5427번: 불
문제 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다. 빌딩
www.acmicpc.net
BFS에서 탈출시간을 구해야 하는 경우 parent부(q.pop()과 for(d < 4) 전)에 탈출조건 배치할 것!
일반적으로 map을 벗어나는 경우 push하지 않는게 맞지만, 해당 문제에서는 map을 벗어나는 경우의 탈출시간을 구해야 한다. pop한 정보를 토대로 parent부에서 탈출 조건을 판단하기 위해서는 map에 벗어난 경우에도 child부에서 push를 해야 한다. 단, 이어지는 push 조건에는 map in이 전제되어야 하므로 map에 벗어나면 push만 해주고 바로 continue해주자.
'이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.'
라는 문제의 조건을 만족시키기 위해서는 불부터 이동시켜야 한다.
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int T, C, R; // 초기화 불필요
string B[1000]; // 초기화 불필요'
int dr[] = { -1, 0, 1, 0};
int dc[] = { 0, 1, 0, -1 };
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> T;
while (T--) {
cin >> C >> R;
for (int r = 0; r < R; ++r) {
cin >> B[r];
}
queue<pair<int, int>> sq, fq;
for (int r = 0; r < R; ++r) {
for (int c = 0; c < C; ++c) {
switch (B[r][c]) {
case '@':
sq.emplace(r, c);
break;
case '*':
fq.emplace(r, c);
break;
}
}
}
int t = 0;
while (!sq.empty()) {
// 불 확산
int fqs = fq.size();
while (fqs--) {
int r = fq.front().first, c = fq.front().second;
fq.pop();
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || R <= nr || nc < 0 || C <= nc || B[nr][nc] == '#' || B[nr][nc] == '*') {
continue;
}
B[nr][nc] = '*';
fq.emplace(nr, nc);
}
}
// 상근 이동
int sqs = sq.size();
while (sqs--) {
int r = sq.front().first, c = sq.front().second;
sq.pop();
if (r < 0 || R <= r || c < 0 || C <= c) {
goto out;
}
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || R <= nr || nc < 0 || C <= nc) {
sq.emplace(nr, nc);
continue;
}
if (B[nr][nc] == '.') {
B[nr][nc] = '@';
sq.emplace(nr, nc);
}
}
}
++t;
}
cout << "IMPOSSIBLE\n";
continue;
out:
cout << t << '\n';
}
return 0;
}