[백준 9376][C++] 탈옥

문제

https://www.acmicpc.net/problem/9376

9376번: 탈옥

 

풀이 과정

[참고 링크 1] [참고 링크 2] [0-1 BFS 알고리즘 링크]

 

필자는 링크 1의 코드를 기반으로 풀이를 작성했다.

 

해당 문제는 0-1 BFS 알고리즘을 통해 다익스트라 알고리즘보다 효율적으로 구현할 수 있다. 주변의 위치에 존재하는 BFS탐색 시, 문이거나 문이 아닌 경우로 나뉘기 때문이다. 

 

이 문제의 핵심은 아래 3가지 경우를 모두 고려해야 한다는 점이다.

1) 1번 죄수가 탈출하며 문을 여는 경우

2) 2번 죄수가 탈출하며 문을 여는 경우 

3) 밖에서부터 문을 여는 경우

 

위 3가지 경우를 모두 고려하지 않는다면, 최소 경로를 찾을 수 없다.

1번 죄수가 최소로 문을 열며 탈출한 경로를 선택한 상황에서 2번 죄수를 탈출시키는 경우 오히려 더 많은 문을 열어야 될 수 있다.

아래의 경우를 예시로 보자.

원본

왼쪽 죄수의 최소 탈출 경로는 아래 그림처럼 3개의 문만 열면 된다. 문을 연 상태는 그 아래와 같다.

왼쪽 죄수 탈출 경로

왼쪽 죄수 탈출 후

이후 상황에서 오른쪽 죄수가 탈출할 때 2개의 문만 추가로 열면 탈출이 가능하다.

오른쪽 죄수 탈출 경로

 

이렇게 하나씩 고려했을 때는 총 5개의 문을 열어 두 죄수가 탈출할 수 있었다. 하지만 이는 최소가 아니다.

 

 

원본 상태로 돌아가서 확인해보면, 겹치는 경로가 있는 가운데 길로 탈출하는 경우 문을 최소로 4개만 열고 탈출할 수 있다.

 

원본

최소 탈출 경로

 

이 처럼 하나의 상황에서 최소를 찾은 뒤 이후 상황을 해결하는 식으로는 문제를 풀 수 없고 모든 경우에 대한 정보를 한 번에 모아서 판단해야 한다.

 

이를 위해 배열을 3차원으로 dist [MAX][MAX][3] 선언한 뒤 3가지 배열의 정보를 종합하여 판단하는 과정에 이용한다.

dist [ i ][ j ][ k ] 배열은 (i, j) 위치까지 진행하기 위해 열어야 할 문의 수를 의미한다. (k=0 일 때 외부, k=1 일 때 1번 죄수, k=2 일 때 2번 죄수 상황)

두 죄수가 탈출할 때 여는 문의 수를 최소로 하려면 최대한 두 죄수가 같은 경로로 탈출해야 한다. 이는 외부로부터 문을 열고 들어오는 상황에 의해 고려된다.

 

이렇게 (i, j) 위치까지 도달하기 위해 열어야 하는 문의 개수를 통해 최적점을 찾았다면 해당 최적점을 통해 답을 얻을 수 있다.

 

 

 

 

 

하지만 여기서 끝이 아니다. [참고 링크 1]의 코드로만 답안을 작성하게 된다면 60%에서 오답을 받게 된다. 그 이유는 아래와 같은 경우가 발생할 수 있기 때문이다.

 

벽에 의해 영역이 분리된 경우

왼쪽 죄수의 영역은 벽에 의해 오른쪽 죄수와 분리되어 있는 상황이다. 이 경우에서는 소스코드 Line 79~81의 세 영역의 정보를 합치는 과정을 수행할 수 없다.

 

(1,1) 위치의 dist 값을 구하면 dist [1][1][0] = 0, dist [1][1][1] = 0, dist [1][1][2] = -1이다.

왜냐하면 (1,1) 위치는 오른쪽 죄수가 이동할 수 없는 칸이기 때문에 초기화한 값 그대로 -1을 띄게 된다.

따라서 정보를 종합하는 덧셈 과정에서 모든 경우에서 방문할 수 없는 칸이라면 덧셈 연산에서 제외시켜야 하므로 Line 78을 추가했다.

 

소스 코드

#include <iostream>
#include <cstring>
#include <deque>
#include <climits>
 
using namespace std;
 
int n;
const int MAX = 102;
int h,w;
 
char a[MAX][MAX];
int dist[MAX][MAX][3];
 
deque<pair<int,int>> dq;
 
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
 
void BFS(){
    //외부에서 문을 열기 시작하는 경우 dq에 입력
    dq.push_back({0,0});
    for(int k=0; k<3; k++){
        int sx = dq.back().first;
        int sy = dq.back().second; 
        dq.pop_back();
 
        deque<pair<int,int>> q;
        q.push_back({sx,sy});
        dist[sx][sy][k] = 0;
 
        while(!q.empty()){
            int x = q.front().first;
            int y = q.front().second;
            q.pop_front();
            for(int i=0; i<4; i++){
                int nx = x+dir[i][0];
                int ny = y+dir[i][1];
                if(nx < 0 || nx > h+1 || ny < 0 || ny > w+1) continue;
                if(dist[nx][ny][k] >= 0 || a[nx][ny] == '*') continue;
                if(a[nx][ny] == '.'){
                    dist[nx][ny][k] = dist[x][y][k];
                    q.push_front({nx,ny});
                }
                else if(a[nx][ny] == '#'){
                    dist[nx][ny][k] = dist[x][y][k]+1;
                    q.push_back({nx,ny});
                }
            }
        }
    }
}
 
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int t;
    cin >> t;
    while(t--){
        memset(dist, -1, sizeof(dist));
        cin >> h >> w;
        for(int i=0;i<h+2;i++){
            for(int j=0;j<w+2;j++){
                //테두리 빈칸으로 채우기
                if(i==0 || i==h+1 || j==0 || j==w+1) a[i][j] = '.';
                else cin >> a[i][j];
                //죄수1, 죄수2 위치에서 문을 열기 시작하는 경우 dq에 입력
                if(a[i][j] == '$'){
                    a[i][j] = '.';
                    dq.push_back({i,j});
                }
            }
        }
        BFS();
        int ans = INT_MAX;
        for(int i=0;i<h+2;i++){
            for(int j=0;j<w+2;j++){
                if(a[i][j] == '*') continue;
                if(dist[i][j][0]==-1 || dist[i][j][1]==-1 || dist[i][j][2]==-1) continue;
                int k = dist[i][j][0] + dist[i][j][1] + dist[i][j][2];
                if(a[i][j] == '#') k-=2;
                if(ans > k) ans = k;
            }
        }
 
        cout << ans << "\n";
    }
 
 
    return 0;
}

 

결과 및 후기

필자는 해당 문제를 처음에 각 죄수의 위치에서 DFS로 방문하는데, 문이 없는 위치부터 방문하고 그 뒤에 문이 있는 위치를 방문하도록 구현하려 했다. 하지만 이렇게 각각 수행한 뒤의 겹치는 경우 처리에서 문제를 겪고 더 풀지 못했었다.

 

이 문제는 deque를 이용한 0-1 BFS를 적용하여 빠르게 구현할 수 있다는 사실과 다익스트라 알고리즘에 대해 다시 공부해보는 좋은 계기가 된 문제라고 생각한다.