[BOJ] 9376 : 탈옥

9376 : 탈옥

풀이

BFS

삼성기출문제.

처음에 풀때는 몇일동안 못풀어서 고생했었는데, 확실히 이제는 실력이 올랐나보다.

이문제가 어려운점은 죄수가 두명이라는 점이다.

이문제를 해결하기위한 스킬은 외부에서 죄수말고도 문을 열어주러 오는 상근이를 가정하는 것이다.

입력된값 말고 테두리에 빈공간을 만들어준다.

테두리는 가중치가 0이므로(문만 가중치1) 아무곳이나 상근이의 출발점을 해도 같다(임의로 0,0으로하자)

그리고는 상근이와 죄수2명을 각각 BFS탐색을 한다.

이때 우선순위큐를 써도 되고, deque를 써도되는데, 이번에는 deque로 풀었다.

(단순히 숫자 몇개만 들어가는 dfs에서는 deque를 쓰는게 더 효율적으로 보인다, 우선순위 큐는 삽입 마다 계속 힙정렬 하니까…)

deque를 이용하면 우선순위를 설정해줄수있다. ‘.’이나 ‘$’(사람)이나 0의 값이면 가중치가 0이므로

덱의 ‘앞’에 넣어준다.

그리고 ‘#’(문)이면 덱의 맨뒤에 넣어준다.(제일 나중에 탐색해야되므로)

뭐 이방법 말고도 cnt를 비교하면서 해도될것같은데, 이게 더 간단하다.

그리고 큐의 front부터 pop해나가면서 탐색하면 된다.

그리고 이문제의 두번째 키포인트는 3가지 탐색결과를 합칠때

문에 해당하는 위치는 값을 2를 빼줘야 된다는 것이다.

왜냐하면 ‘#’에서 1명만 문열면 되는데 3명이 문연결로 3중첩되있기 때문이다.

이렇게 합친 값중에 최소값이 답이다.

코드

#include <iostream>
#include <cstring>
#include <queue>
#include <deque>
using namespace std;

typedef struct p {
    int x;
    int y;
    int cnt;
}p;

const int dx[] = { -1,0,1,0 };
const int dy[] = { 0,1,0,-1 };
//입력보다 바깥에 0을 남김
char arr[102][102];
int h, w;
int x_1, x_2;
int y_1, y_2;

int chk[102][102][3];
//마지막에 각 chk를 합칠것
int sumArr[102][102];

//시작x,y 그리고 type:0은 외부인, 1은 x1,y1, 2는 x2,y2
void bfs(int sx, int sy, int type) {
    //deque를 이용해서 문이 아닌것부터 우선 앞에 넣어줄예정
    deque<p> q;
    q.push_back({sx,sy,0});
    chk[sx][sy][type] = 0;
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int cnt = q.front().cnt;
        q.pop_front();
        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if (nx >= 0 && nx <= h + 1 && ny >= 0 && ny <= w + 1) {
                if (chk[nx][ny][type] == -1) {
                    if (arr[nx][ny] == '.' || arr[nx][ny] == '$' || arr[nx][ny]==0) {
                        chk[nx][ny][type] = cnt;
                        q.push_front({nx,ny,cnt});
                    }
                    else if (arr[nx][ny] == '#') {
                        chk[nx][ny][type] = cnt + 1;
                        q.push_back({nx,ny,cnt+1});
                    }
                }
            }
        }
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        memset(arr, 0, sizeof(arr));
        memset(chk, -1, sizeof(chk));
        memset(sumArr, 0, sizeof(sumArr));
        cin >> h >> w;
        char trash;
        scanf("%1c", &trash);
        //입력보다 바깥에 0을 남김
        int flag = 0;
        for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= w; j++) {
                scanf("%1c", &arr[i][j]);
                if (arr[i][j] == '$' && flag) {
                    x_1 = i;
                    y_1 = j;
                }
                else if (arr[i][j] == '$') {
                    x_2 = i;
                    y_2 = j;
                    flag = 1;
                }
            }
            scanf("%1c", &trash);
        }
        bfs(0, 0, 0);
        bfs(x_1, y_1, 1);
        bfs(x_2, y_2, 2);

        int ans = 987654321;
        //합쳐서 최소를 찾자
        for (int i = 0; i <= h + 1; i++) {
            for (int j = 0; j <= w + 1; j++) {
                //'#'이라면 3번중첩이므로 2를 빼준다.
                if (arr[i][j] == '#')
                    sumArr[i][j] -= 2;
                for (int k = 0; k < 3; k++) {
                    sumArr[i][j] += chk[i][j][k];
                }
                if (sumArr[i][j] != -3 && sumArr[i][j] < ans)
                    ans = sumArr[i][j];
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

Written on April 10, 2019