• 문제 : https://www.acmicpc.net/problem/4179

---

1. 문제 접근

• 불의 이동 최단거리와 사람 이동거리 최단거리와 비교해야 한다.
• 동일한 가중치의 최단거리는 BFS로 풀기
• 화재는 여러 군데서 일어날 수도 있고, 아예 발생하지 않을 수도 있다.

---

2. 시행착오

• BFS로 접근하는 것은 했으나, 불이 번지는 것과 사람이 이동하는 것을 어떻게 비교할지 하는 방법에서 헤맸다.

---

3. 코드 및 풀이

3.1 풀이

신경써야 할 점
1. 불이 이동하는 좌표평면을 처음에 가장 큰 값인 INF로 초기화해줘야 함(화재가 아예 발생하지 않는 경우도 존재)
2. 사람이 탈출할 때, 가장자리로 나가는 점을 따로 구현해야 함

• 우선, 불의 이동경로를 fire이라는 이차원 배열에 기록한다.
  • INF로 초기화했기 때문에, 한 번도 방문하지 않은 경우는 INF값을 가지기 때문에, 고려해서 BFS 돌리기
• 그 후 사람 이동경로를 기록한다.
  • ny, nx 반복문 이전에, 현재 위치가 가장자리인지 아닌지 확인해줘야 한다.(가장자리에 있으면 무조건 탈출할 수 있기 때문)
  • fire[ny][nx] <= visited[y][x] + 1 조건을 통해, 내가 다음에 갈 위치까지 걸리는 시간이, 그 위치까지 화재가 날 걸리는 시간보다 크거나 같으면, 무시.
  • while 종료조건은 q가 빌때까지 계속되므로, 만약 가장자리로 가기 전에 q가 비어버리면 자동종료.

#include <bits/stdc++.h>
using namespace std;

const int INF = 987654321;
const int max_l = 1004;
const int dy[4] = {0, 1, 0, -1};
const int dx[4] = {1, 0, -1, 0};

int R, C, ny, nx, ret;
pair<int, int> p;
char adj[max_l][max_l];
int fire[max_l][max_l];
int visited[max_l][max_l];

queue<pair<int, int>> fire_q;
queue<pair<int, int>> q;

bool isValid(int y, int x){
    return 0 <= y && y < R && 0 <= x && x < C;
}

int main(){
    cin >> R >> C;
    fill(&fire[0][0], &fire[0][0] + max_l * max_l, INF);
    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            cin >> adj[i][j];
            if(adj[i][j] == 'F') {
                fire[i][j] = 1; fire_q.push({i, j});
            }
            else if(adj[i][j] == 'J') {
                p.first = i; p.second = j;
            }
        }
    }
    
    // 불 이동 기록
    while(fire_q.size()) {
        int y, x;
        tie(y, x) = fire_q.front(); fire_q.pop();
        for(int i = 0; i < 4; i++){
            ny = y + dy[i];
            nx = x + dx[i];
            if(!isValid(ny, nx)) continue;
            if(adj[ny][nx] == '#' || fire[ny][nx] != INF) continue;
            fire[ny][nx] = fire[y][x] + 1;
            fire_q.push({ny, nx});
        }
    }
    
    // 사람 이동기록 기록
    visited[p.first][p.second] = 1;
    q.push(p);
    bool flag = false;
    while(q.size()){
        int y, x;
        tie(y, x) = q.front(); q.pop();
		if(x == C-1 || y == R-1 || x == 0 || y == 0){
            ret = visited[y][x];
            flag = true;
            break;
		}
        for(int i = 0; i < 4; i++){
            ny = y + dy[i];
            nx = x + dx[i];
            if(!isValid(ny, nx)) continue;
            // 이미 방문했으면
            if(visited[ny][nx]) continue;
            // 벽이거나, 불이 사람의 움직임보다 더 빠르거나 같게 퍼졌을 때
            if(adj[ny][nx] == '#' || fire[ny][nx] <= visited[y][x] + 1) continue;
            visited[ny][nx] = visited[y][x] + 1;
            q.push({ny, nx});
        }
    }
    
    if(flag) cout << ret;
    else cout <<"IMPOSSIBLE";
    
}

---

Reference