[백준 5427] 불

작성일 | In |

문제 링크

https://www.acmicpc.net/problem/5427

풀이

불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나가기 때문에 BFS를 이용해서 시간에 따라 불이 붙는 위치를 알 수 있습니다. 그러므로 각 격자마다 불이 붙는 시간을 기록하고 상근이가 격자에 불이 붙는 시간보다 빠른 시간안에만 방문할 수 있도록 BFS로 격자 밖으로 나가는 가장 빠른 시간을 구할 수 있습니다.

위처럼 구현한다면 BFS도 2번 구현해야하고 변수도 따로 관리해야 하는 만큼 번거롭겠지만 한번의 BFS만 이용하는 방법이 있습니다. 상근이와 불이 같은 시간에 한 격자에 도달하는 경우 불이 그 격자로 옮겨져서 상근이는 이동하지 못하기는 것을 처리하는 걸 하나의 큐로 이용하는 것은 어려워 보일지 몰라도 (큐를 2개 사용해도 되긴 하겠지만 이 방법 또한 구현이 번거롭습니다.) 큐에 들어간 순서대로 BFS가 퍼져나가는 특성을 이용해 불이 있는 격자들을 먼저 큐에 넣고 상근이를 마지막에 큐에 넣는다면 불이 먼저 옮겨붙은 다음에 불이 붙지 않은 격자로 상근이가 이동하게 됩니다. 그러므로 정답은 BFS 1번만에 구할 수 있기에 전체 시간복잡도는 $O(NM)$입니다. 자세한 구현 방법은 코드를 참고해주세요.

전체 코드

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int tc, n, m, chk[1010][1010], dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
char s[1010][1010];

int main(){
    scanf("%d",&tc);
    while(tc--){
        memset(chk, 0, sizeof(chk));
        scanf("%d %d",&m,&n);
        for(int i=1;i<=n;i++) scanf("%s",s[i]+1);

        queue<tuple<int, int, int, int>> q;

        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(s[i][j] == '*') q.push({i, j, 0, 1}), chk[i][j] = 1;
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(s[i][j] == '@') q.push({i, j, 0, 0}), chk[i][j] = 1;

        int ans = 0;
        while(!ans && !q.empty()){
            auto [x, y, c, t] = q.front(); q.pop();

            for(int i=0;i<4;i++){
                int xx = x + dx[i], yy = y + dy[i];
                if(chk[xx][yy] || s[xx][yy] == '#') continue;
                if(xx < 1 || yy < 1 || xx > n || yy > m){
                    if(!t){
                        ans = c+1;
                        break;
                    }
                    continue;
                }
                chk[xx][yy] = 1, q.push({xx, yy, c+1, t});
            }
        }

        if(ans) printf("%d\n",ans);
        else printf("IMPOSSIBLE\n");
    }
}