불!
문제 해석
미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기 전에 탈출할 수 있는 지 여부를 결정하는 문제입니다.
설계(10)
큐를 두개 사용하는 BFS문제입니다.
순서는 불을 먼저 퍼뜨린 후, 지훈이가 이동할 수 있는지 여부를 판단하도록 합니다.
여기서 주의 해야할 점은 불의 시작지점이 없을 수도 있고, 여러개 있을 수도 있다는 점입니다.
구현(15)
코드
#include <iostream>
#include <queue>
using namespace std;
#define MAXN 1000
char arr[MAXN][MAXN];
int R, C;
queue<pair<int, int> > q, fq;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int bfs() {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (arr[i][j] == 'J') {
q.push({ i,j });
}
else if (arr[i][j] == 'F') {
fq.push({ i,j });
}
}
}
int time = 0;
while (!q.empty()) {
int q_size = fq.size();
while (q_size--) {
int x = fq.front().first;
int y = fq.front().second;
fq.pop();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || ny < 0 || nx >= R|| ny >= C) continue;
if (arr[nx][ny] == 'J' || arr[nx][ny] == '.') {
arr[nx][ny] = 'F';
fq.push({ nx,ny });
}
}
}
q_size = q.size();
while (q_size--) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if (x == 0 || y == 0 || x == R-1 || y == C-1) return time+1;
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
if (arr[nx][ny] == '.') {
arr[nx][ny] = 'J';
q.push({ nx,ny });
}
}
}
time++;
}
return -1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> R >> C;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
char tmp;
cin >> tmp;
arr[i][j] = tmp;
}
}
int ans = bfs();
if (ans == -1) cout << "IMPOSSIBLE\n";
else cout << ans << "\n";
}
디버깅
앞서 언급했던 주의할 점을 간과하였습니다.
예시에서 볼 수 있듯이 불이 한개만 있는 것으로 어림짐작하여 풀이를 하였습니다.
제출결과
36 ms
마무리
두개의 큐를 이용한 BFS문제였습니다.
문제의 조건이 없다면 모든 경우를 고려해야한다는 점을 상기시켜주는 문제였습니다.