[백준 4179] 불

[백준 4179] 불

문제 링크

#include "header.h"
using namespace std;
int R, C;
char map_[1001][1001];
int visit[1001][1001];
int fire_map[1001][1001];

int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
pair <int, int> jihoon;
queue <pair<int, int>> fire;

void input(){
    cin >> R >> C;

    for(int i=0; i<R; i++){
        for(int j=0; j<C; j++){
            cin >> map_[i][j];
            if(map_[i][j] == 'J'){
                jihoon = {i, j};
                map_[i][j] = '.';
            }
            if(map_[i][j] == 'F'){
                fire.push({i, j});
                fire_map[i][j] = 1;
            }
        }
    }
}
void spread_fire(){

    while (!fire.empty()){
        int top_x = fire.front().first;
        int top_y = fire.front().second;
        fire.pop();

        for(int i=0; i<4; i++){
            int nx = top_x + dx[i];
            int ny = top_y + dy[i];
            if(fire_map[nx][ny] || map_[nx][ny] == '#' || nx < 0 || ny < 0 || nx >= R || ny >= C) continue;

            fire_map[nx][ny] = fire_map[top_x][top_y] + 1;
            fire.push({nx, ny});
        }
    }
}
void solve(){

    spread_fire();

    queue <pair<int, int>> q;
    visit[jihoon.first][jihoon.second] = 1;
    q.push({jihoon.first, jihoon.second});
    int flag = 0;
    int ans = 0;
    while (!q.empty()){
        int top_x = q.front().first;
        int top_y = q.front().second;
        q.pop();

        for(int i=0; i<4; i++){
            int nx = top_x + dx[i];
            int ny = top_y + dy[i];
            if(map_[nx][ny] == '#' || visit[nx][ny]) continue;

            if(nx < 0 || ny < 0 || nx >= R || ny >= C){ //탈출 한 경우
                flag = 1;
                ans = visit[top_x][top_y];
                break;
            }
            
            if(fire_map[nx][ny] && fire_map[nx][ny] <= visit[top_x][top_y] + 1) {
                flag = 0;
                continue;
            }

            q.push({nx, ny});
            visit[nx][ny] = visit[top_x][top_y] + 1;
        }
        if(flag) break;
    }

    if(!flag) cout << "IMPOSSIBLE" << endl;
    else cout << ans << endl;
}
int main() {
    input();
    solve();
    return 0;
}

• bfs로 풀었다.
• 일단 불을 bfs돌려서 퍼지는 날짜를 update 해 준다.
• 그 다음 지훈이를 움직이는데, 이 때 이미 불이 퍼진 날짜는 피해서 움직여준다.
• 불이 없는 경우를 판별하기 위해서, 가장자리 체크 할 때 fire_map[nx][ny]가 있는지 체크 해 준다.