[BOJ/5427번불!] c++ / BFS

문제

상근이가 불이 난 곳을 피해 탈출하는데 걸리는 최소 시간을 구하는 문제

-불이 탈출구까지 번질 경우, IMPOSSIBLE 출력

-불은 *, 상근이는 @, 벽은 #, 빈 공간은 . 

 

생각

불이 붙으려는 칸으로는 상근이가 이동할 수 없다는걸 생각했을 때 불을 먼저 큐에 넣어야 함

상근이가 탈출하면 함수가 종료되어야 함

 

문제풀이

1.불이 난 위치 방문표시( -1 ) + 큐에 푸쉬

2.상근이 위치 방문표시( 1 ) + 큐에 푸쉬

3.BFS 탐색

3-1.상근이가 기준칸이고 정해진 범위에서 벗어난 x, y 값이 나온다면, vis[x][y] 반환 ( 탈출 성공 )

3-2.상근이가 아닌 기준칸이고 정해진 범위에서 벗어난  x, y 값이 나온다면, continue

4.기준칸이 불이고 방문하지 않은 빈 공간이 나온다면, 방문표시( -1 ) + 큐에 푸쉬

4-1.기준칸이 상근이고 방문하지 않은 빈 공간이 나온다면, 방문표시( 1 ) + 큐에 푸쉬

5.큐가 빌때까지 탈출하지 못한다면, -1 반환

6.result값이 -1이면, "IMPOSSIBLE" 출력

6-1.그렇지 않으면, result값 출력

7.map과 vis 초기화

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define X first
#define Y second
string map[1001];
int vis[1001][1001];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int T, w, h, ex, ey, result=0;
int BFS() {
    queue<pair<int, int>> Q;

    for ( int i = 0; i < h; i++ )
        for ( int j = 0; j < w; j++ ) {
            if ( map[i][j] == '*' ) {
                vis[i][j] = -1;
                Q.push({i, j});
            }
        }

    for ( int i = 0; i < h; i++ )
        for ( int j = 0; j < w; j++ ) {
            if ( map[i][j] == '@') {
                vis[i][j] = 1;
                Q.push({i, j});
            }
        }

    while(!Q.empty()) {
        pair<int, int> cur = Q.front(); Q.pop();

        for ( int dir = 0; dir < 4; dir++ ) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            
            if ( vis[cur.X][cur.Y] <= 0 && (nx < 0 || nx >= h || ny < 0 || ny >= w )) continue;
            if ( vis[cur.X][cur.Y] > 0 && (nx < 0 || nx >= h || ny < 0 || ny >= w ))
                return vis[cur.X][cur.Y];
            
            if ( vis[nx][ny] || map[nx][ny] == '#') continue;

            if ( vis[cur.X][cur.Y] == -1  && map[nx][ny] == '.' ) { // 불 확장
                vis[nx][ny] = -1;
                Q.push({nx, ny});
            }

            else if ( vis[cur.X][cur.Y] > 0 && map[nx][ny] == '.' ) { // 상근이 이동
                vis[nx][ny] = vis[cur.X][cur.Y] + 1;
                Q.push({nx, ny});
            }
        }
    }
    return -1;
}
int findExit() {
    for ( int i = 0; i < h; i++ )
        for ( int j = 0; j < w; j++ )
            if ( i == 0 || i == h-1 || j == 0 || j == w-1 ) {
                if ( vis[i][j] > 0 )
                    return vis[i][j];
            }

    return -1;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> T;
    for ( int c = 0; c < T; c++ ) { 
        cin >> w >> h;
        for ( int i = 0; i < h; i++ ) 
            cin >> map[i];
        
        result = BFS();

        if ( result == -1 )
            cout << "IMPOSSIBLE" << '\n';
        else 
            cout << result << '\n';

        for ( int j = 0; j < h; j++ ) {
            for ( int k = 0; k < w; k++ ) {
                vis[j][k] = 0;
                map[j][k] = 0;
            }
        }
    }
}