백준 g4 불 c++

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

 

풀이

 

1. 불이 퍼지는 시간을 나타내는 fireVis를 만든다. (BFS)

2. 상근이 위치를 BFS로 돌리면서

    벽이거나, 불이 더 이전에 번진 곳이거나(상근이가 방문하는 시간보다 불이 퍼진 시간이 더 작을 때), 범위를 넘어가는 곳은 제외한다.

    이때 불이 퍼진 시간이 0일 때는 불이 퍼지지 않았으면서 상근이가 방문하는 시간보다 작으므로, 예외처리 해주어야 한다.

 

고려한 것

1. 처음에는 불이 0초일 때 시작할 수 있으니 -1로 초기화하고 0부터 시작했으나 그냥 처음 시작을 1로 통일했다

 

/*boj g4 5427 불*/
#include <iostream>
#include <queue>
#define MAXN 1005
using namespace std;

int T, M, N;
int board[MAXN][MAXN];
int fire[MAXN][MAXN];
int vis[MAXN][MAXN];
queue<pair<int, int>> fireQ;
pair<int, int> start;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

void printVis() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cout << vis[i][j] << " ";
        }
        cout << '\n';
    }
}

void initialize() {
    for (int i = 0; i < MAXN; i++) {
        for (int j = 0; j < MAXN; j++) {
            board[i][j] = 0;
            fire[i][j] = 0;
            vis[i][j] = 0;
        }
    }

    while (!fireQ.empty())
        fireQ.pop();
}

void input() {
    initialize();
    cin >> M >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            char a = cin.get();
            while (a != '#' && a != '*' && a != '@' && a != '.')
                a = cin.get();

            // 벽은 1, 상근이 시작은 2, 불은 3, 빈공간은 0
            if (a == '#')
                board[i][j] = 1;
            else if (a == '@') {
                board[i][j] = 2;
                start.first = i;
                start.second = j;
            } else if (a == '*') {
                board[i][j] = 3;
                fireQ.push({i, j});
                fire[i][j] = 1;
            } else
                board[i][j] = 0;
        }
    }
}

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

        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];

            if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if (board[nx][ny] == 1) continue;
            if (fire[nx][ny] > 0) continue;

            fire[nx][ny] = fire[cur.first][cur.second] + 1;
            fireQ.push({nx, ny});
        }
    }
}

void BFS() {
    queue<pair<int, int>> Q;

    vis[start.first][start.second] = 1;
    Q.push({start.first, start.second});

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

        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];

            if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if (board[nx][ny] == 1 || board[nx][ny] == 3) continue;
            if (vis[nx][ny] > 0) continue;
            if (fire[nx][ny] != 0 && vis[cur.first][cur.second] + 1 >= fire[nx][ny]) continue;

            vis[nx][ny] = vis[cur.first][cur.second] + 1;
            Q.push({nx, ny});
        }
    }
}

void output() {
    int mn = 99999999;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (i == 0 || i == N - 1 || j == 0 || j == M - 1) {
                if (vis[i][j] > 0)
                    mn = min(mn, vis[i][j]);
            }
        }
    }
    if (mn == 99999999)
        cout << "IMPOSSIBLE\n";
    else
        cout << mn << "\n";
}
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while (T--) {
        input();
        // 1. 불 퍼지는 거 계산
        fireBFS();

        // 2. 상근이 BFS 계산
        BFS();

        // 3. 결과 출력
        output();
        // printVis();
    }
}