[BOJ] 9376. 탈옥

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

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

 

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

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

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

 

 

#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; }