[BOJ] 백준 4179 불! c++ (bfs)

문제 출처 : https://www.acmicpc.net/problem/4179

4179번: 불!

---

풀이

이 문제는 불과 지훈이의 이동경로를 비교를 해야한다. 따라서 먼저 불의 시간 별 이동경로를 저장하는 배열을 만들어 계산한 뒤,

지훈이가 이동 가능한지 비교한다.

 

불 이동 경로

• 초기 입력 시 fire 배열은 INF로 초기화하고, 처음 불이 있던 자리만 0으로 저장한다.
• bfs로 기존 배열 값보다 값이 작으면 갱신하고 큐에 푸시해준다.

int fire[1000][1000];
queue<pair<int, int>> fire_q; // row, col
void make_fire(){
    while(!fire_q.empty()){
        int row = fire_q.front().first;
        int col = fire_q.front().second;
        fire_q.pop();

        for(int i = 0; i < 4; i++){
            int nRow = row + dy[i];
            int nCol = col + dx[i];
            if(nRow < 0 || nRow >= R || nCol < 0 || nCol >= C || arr[nRow][nCol] == '#')
                continue;
            if(fire[nRow][nCol] > fire[row][col] + 1){
                fire[nRow][nCol] = fire[row][col] + 1;
                fire_q.push({nRow, nCol});
            }
        }
    }
}

지훈이와 불 비교

• 초기 지훈이 위치부터 bfs를 돌려 fire 배열보다 시간이 작으면 큐에 푸시한다!

---

코드

#include <iostream>
#include <queue>
#include <limits.h>

using namespace std;

int R, C;
char arr[1000][1000];
int fire[1000][1000];
bool visit[1000][1000];

queue<pair<int, int>> fire_q; // row, col
pair<int,int> start;

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

struct moves{
    int row;
    int col;
    int cnt;
};

void make_fire(){
    while(!fire_q.empty()){
        int row = fire_q.front().first;
        int col = fire_q.front().second;
        fire_q.pop();

        for(int i = 0; i < 4; i++){
            int nRow = row + dy[i];
            int nCol = col + dx[i];
            if(nRow < 0 || nRow >= R || nCol < 0 || nCol >= C || arr[nRow][nCol] == '#')
                continue;
            if(fire[nRow][nCol] > fire[row][col] + 1){
                fire[nRow][nCol] = fire[row][col] + 1;
                fire_q.push({nRow, nCol});
            }
        }
    }
}

int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> R >> C;
    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            fire[i][j] = INT_MAX;
            cin >> arr[i][j];
            if(arr[i][j] == 'J'){
                start.first = i;
                start.second = j;
            }
            else if(arr[i][j] == 'F'){
                fire_q.push({i, j});
                fire[i][j] = 0;
            }
        }
    }

    make_fire();

    queue<moves> q;
    q.push({start.first, start.second, 0});
    visit[start.first][start.second] = true;
    bool flag = false;
    while(!q.empty()){
        int row = q.front().row;
        int col = q.front().col;
        int cnt = q.front().cnt;
        q.pop();
        visit[row][col] = true;

        if(row == 0 || row == R-1 || col == 0 || col == C-1){
            cout << cnt + 1;
            return 0;
        }
        for(int i = 0; i < 4; i++){
            int nRow = row + dy[i];
            int nCol = col + dx[i];
            if(nRow < 0 || nRow >= R || nCol < 0 || nCol >= C || arr[nRow][nCol] == '#' || visit[nRow][nCol])
                continue;

            if(fire[nRow][nCol] > cnt + 1){
                visit[nRow][nCol] = true;
                q.push({nRow, nCol, cnt+1});
            }
        }
    }
    cout << "IMPOSSIBLE";
    return 0;
}