[백준 9376] 탈옥

문제

www.acmicpc.net/problem/9376

 

알고리즘

01BFS

 

풀이

한 사람이 두 죄수를 탈옥시키기 위한 최소 문의 수를 구하는 문제입니다.

 

3인 통화문제와 마찬가지로 세 사람의 위치를 구한 후 다익스트라를 세번 사용하면 풀 수 있는 문제입니다. 죄수의 위치는 주어지지만 구출하는 사람의 위치는 주어지지 않습니다. 주어지는 공간(N X M)을 테두리를 확장하여 (N+2 X M+2)로 만듭니다. 이렇게하면 구출하는 사람의 위치를 임의로 (0,0)으로 설정해도 됩니다.

 

BFS는 이동에 사용하는 값이 모두 동일할 때, queue를 사용해서 원하는 목표까지의 거리를 구하게 됩니다. 다익스트라는 이동에 사용하는 값이 다를 때 사용하는데, 가중치가 0과 1로만 주어져 있을 때는 다익스트라보다 더 빠르게 동작하는 01BFS를 사용할 수 있습니다. 일반적인 BFS와 다른점은 queue대신 deque를 사용해서 구현하는 점입니다. 이 문제는 그냥 이동할 때 사용하는 가중치 0과 문을 열때 사용하는 가중치 1, 두가지로만 이루어져 있으므로 01BFS를 통해 문제해결이 가능합니다.

 

사람마다 01BFS를 수행한 결과들을 합하게 되면 동일한 문에 대해서 여러번 여는 경우를 처리를 하지 않았으므로 마지막으로 문에 해당하는 위치는 2를 빼주면 최솟값을 구할 수 있습니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

template<typename A, typename T, size_t N>
void Fill(A (&array)[N], const T& val) {
    fill((T*)array, (T*)(array + N), val);
}

const int dy[4] = { 1, -1, 0, 0 };
const int dx[4] = { 0, 0, 1, -1 };
typedef pair<int, int> pii;

int tc, N, M;
int board[100 + 5][100 + 5];
int dist[3][100 + 5][100 + 5];

bool inr(int y, int x) {
    return 0 <= y && y <= N + 1 && 0 <= x && x <= M + 1;
}

void bfs01(int r, int c, int person) {
    dist[person][r][c] = 0;
    deque<pii> dq;
    dq.emplace_back(r, c);

    while (!dq.empty()) {
        auto [R, C] = dq.front();
        dq.pop_front();
        rep(i, 4) {
            int NR = R + dx[i];
            int NC = C + dy[i];
            if (!inr(NR, NC) || board[NR][NC] == -1 || dist[person][NR][NC] != INT_MAX / 3)
                continue;

            dist[person][NR][NC] = dist[person][R][C] + board[NR][NC];
            if (board[NR][NC] == 1) {
                dq.emplace_back(NR, NC);
            } else if (board[NR][NC] == 0) {
                dq.emplace_front(NR, NC);
            }
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> tc;
    while (tc--) {
        vector<pii> prisoner;
        memset(board, 0, sizeof(board));
        Fill(dist, INT_MAX / 3);
        cin >> N >> M;
        REP(i, N) REP(j, M) {
            char x;
            int conv = 0;
            cin >> x;

            switch (x) {
            case '*': {
                conv = -1;
                break;
            }
            case '#': {
                conv = 1;
                break;
            }
            case '$': {
                prisoner.emplace_back(i, j);
                break;
            }
            }
            board[i][j] = conv;
        }
        prisoner.emplace_back(0, 0);
        rep(i, 3) {
            bfs01(prisoner[i].first, prisoner[i].second, i);
        }

        REP(k, 2) {
            for (int i = 0; i <= N + 1; ++i) {
                for (int j = 0; j <= M + 1; ++j) {
                    dist[0][i][j] += dist[k][i][j];
                }
            }
        }
        int ans = INT_MAX;
        for (int i = 0; i <= N + 1; ++i) {
            for (int j = 0; j <= M + 1; ++j) {
                if (board[i][j] == 1)
                    dist[0][i][j] -= 2;
                ans = min(ans, dist[0][i][j]);
            }
        }
        cout << ans << '\n';
    }
    return 0;
}