[BOJ] 탈옥

[BOJ] 탈옥

Problem URL : 탈옥

#include <cstring>
#include <deque>
#include <vector>
#include <iostream>
#define p pair<int,int>

using namespace std;

int h, w;
char map[102][102];
int dist[102][102][3];
vector<p> people;
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };

void bfs(int nth) {
    deque<p> dq;
    dq.push_front({ people[nth].first, people[nth].second });
    dist[people[nth].first][people[nth].second][nth] = 0;
    while (!dq.empty()) {
        int x = dq.front().first;
        int y = dq.front().second; 
        dq.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 || dist[nx][ny][nth] >= 0 || map[nx][ny] == '*') continue;
            if (map[nx][ny] == '.') {
                dist[nx][ny][nth] = dist[x][y][nth];
                dq.push_front({ nx, ny }); // dist가 증가하지 않았으므로 우선탐색
            } else if (map[nx][ny] == '#') {
                dist[nx][ny][nth] = dist[x][y][nth] + 1;
                dq.push_back({ nx, ny }); // dist가 증가했으므로 나중에 탐색
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int TC;
    cin >> TC;
    for (int tc=1; tc <=TC; tc++) {
        memset(dist, -1, sizeof(dist));
        memset(map, '.', sizeof(map));
        people.clear();
        cin >> h >> w;
        
        for (int i = 1; i <= h; i++) {
            string str = "";
            cin >> str;
            for (int j = 1; j <= w; j++) {
                map[i][j] = str[j - 1];
                if (map[i][j] == '$') {
                    map[i][j] = '.';
                    people.push_back({ i, j });
                }
            }
        }
        people.push_back({ 0,0 });
        for (int i = 0; i < 3; i++) {
            bfs(i);
        }
        int ans = 1e9;
        for (int i = 0; i <= h + 1; i++) {
            for (int j = 0; j <= w + 1; j++) {
                if (map[i][j] == '*') continue;
                int cnt = dist[i][j][0] + dist[i][j][1] + dist[i][j][2];
                if (cnt == -3) continue; // [1]
                if (map[i][j] == '#') cnt -= 2; // [2]
                if (ans > cnt) ans = cnt;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Comments

[1] 이 조건이 없으면 다음과 같은 반례가 생긴다.

1  
7 7  
***#***  
*.....*  
*.***.*  
*#*.*#*  
*.***.*  
*.$*$.*  
*******

즉 이동할 수 없는 공간이 있으면 그곳은 dist가 갱신이 안되고 세개의 dist가 -1값을 갖는다.

[2] 세가지 dist를 더할 때 벽(‘#’) 위치에서 더하면 3번 중복된다. 그래서 -2를 해주자.