백준 4179 불! (C++)

4179번: 불!

bfs를 이용한 문제이다. 문제 상황을 보면 지훈이와 불은 한 타임에 동시에 움직인다. 그렇기에 입력을 받을 때 지훈이의 위치와 불의 위치를 따로 저장한 뒤 큐에 넣어주었다. 주의할 점은 지훈이부터 큐에 넣어줘야한다는 점이다. 이유는 bfs를 돌 때 불의 경우 배열의 값을 F로 바꿔주면서 이동하기 때문에 불 먼저 이동할 경우 아직 이동하지 않은 J를 없애버려 위치를 찾을 수 없게되기 때문이다. bfs를 돌면서 J와 F일 경우를 나눠주어 각각의 조건에 따라 큐에 넣어주고 J일 때 가장자리에 도착할 경우를 구해 시간을 저장한 뒤 출력해주었다.
쉽게 풀 수 있었던 문제였다. 제출 기록을 보니 22년 5월에 문제를 풀다가 포기했는지 재채점으로 실패했는지 실패로 되어있던 문제였는데 이번에는 쉽게 통과할 수 있었다. 아마 그동안 많이 성장한게 아닐까 싶다. bfs 관련 문제는 확실히 자신감이 많이 붙었다는 것을 느낄 수 있었다.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int R, C, jy, jx, result = 0;
string A[1000];
queue<pair<pair<int, int>, int>> q;
vector<pair<int, int>> fire;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

void bfs() {
    q.push({ {jy,jx}, 0 });

    for (int i = 0; i < fire.size(); i++) {
        int y = fire[i].first;
        int x = fire[i].second;

        q.push({ {y,x},0 });
    }

    while (!q.empty()) {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int time = q.front().second;

        if (A[y][x] == 'J' && (y == 0 || y == R - 1 || x == 0 || x == C - 1)) {
            result = time + 1;
            break;
        }

        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= R || nx >= C) continue;

            if (A[y][x] == 'J') {
                if (A[ny][nx] != '.') continue;

                q.push({ {ny,nx},time + 1 });
                A[ny][nx] = 'J';
            }
            else if (A[y][x] == 'F') {
                if (A[ny][nx] == '#' || A[ny][nx] == 'F') continue;

                q.push({ {ny,nx},time + 1 });
                A[ny][nx] = 'F';
            }
        }
    }
}

void solution() {
    bfs();

    if (result == 0) cout << "IMPOSSIBLE";
    else cout << result;
}

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

    cin >> R >> C;

    for (int i = 0; i < R; i++) {
        cin >> A[i];

        for (int j = 0; j < C; j++) {
            if (A[i][j] == 'J') {
                jy = i;
                jx = j;
            }
            else if (A[i][j] == 'F') {
                fire.push_back({ i,j });
            }
        }
    }

    solution();

    return 0;
}