[BOJ] 9376. 탈옥

*세 지점에서 bfs를 실행한다.

상근이(0,0) / 죄수 2명

 

*상근이는 건물 밖을 마음대로 나다닐 수 있기 때문에 맵의 크기를 0,0~h+1, w+1으로 잡아줘야 한다.

*상근이를 포함한 각 죄수들이 건물 밖으로 향하는데 여는 문의 개수를 dist[][]에 저장한다.

*각 죄수들이 문을 열고 나가도록 코드를 작성하지만 실제로는 상근이가 두 죄수를 데리고 가기 때문에 세 명 다 문을 열 수 있는 가능성을 없애줘야 한다. (정답으로 요구한 것은 최소값이기 때문에)

 

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98

#include <iostream> #include <vector> #include <queue> #include <cstring> #include <functional> /* BOJ 9476.탈옥 */ using namespace std;   int h, w; char map[102][102]; typedef pair<int, int> pp; typedef pair<int, pp> ipp; vector<pp> prison; int dist[102][102], c_dist[102][102];   int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };   void bfs(int idx) {     priority_queue<ipp, vector<ipp>, greater<ipp>> q;     q.push(ipp(0,prison[idx]));           memset(c_dist, -1, sizeof(c_dist));     c_dist[prison[idx].first][prison[idx].second] = 0;       while (!q.empty()) {         int x = q.top().second.first;         int y = q.top().second.second;         int d = q.top().first;         q.pop();           for (int i = 0; i < 4; i++) {             int nx = x + dx[i];             int ny = y + dy[i];               if (nx < 0 || nx > h + 1 || ny < 0 || ny > w + 1 || c_dist[nx][ny] != -1 || map[nx][ny] == '*') continue;               if (map[nx][ny] == '#' ) {                 c_dist[nx][ny] = d+1;                 q.push(ipp(c_dist[nx][ny],pp(nx, ny)));             }             else {                 c_dist[nx][ny] = d;                 q.push(ipp(c_dist[nx][ny], pp(nx, ny)));             }         }     }     for (int i = 0; i <= h + 1; i++) {         for (int j = 0; j <= w + 1; j++) {                           dist[i][j] += c_dist[i][j];         }     }     } int main() {       ios_base::sync_with_stdio(0);     cin.tie(0);       int t;     cin >> t;     while (t--) {         prison.clear();         cin >> h >> w;         memset(map, ' ', sizeof(map));         memset(dist, 0, sizeof(dist));           prison.push_back({ 0,0 });         for (int i = 1; i <= h; i++) {             for (int j = 1; j <= w; j++) {                 cin >> map[i][j];                 if (map[i][j] == '$') {                     prison.push_back({ i, j });                 }             }         }         //각 죄수마다 탈출하기 위해 문을 여는 횟수를 저장한다. (dist에)         for (int i = 0; i < 3; i++) {             bfs(i);         }           int ans = 987654321;         for (int i = 0; i <= h + 1; i++) {             for (int j = 0; j <= w + 1; j++) {                 if (map[i][j] == '*') continue;                 if (map[i][j] == '#') dist[i][j] -= 2; //세 명이 동시에 열었을 가능성을 없앤다.                 ans = ans > dist[i][j] ? dist[i][j] : ans;             }         }         cout << ans << '\n';               }           return 0; }