1. 풀이

문제 요약

불은 4방향 모두로 퍼지고, 지훈이는 4방향 중 하나로 움직인다.

지훈이가 불을 피해서 가장자리에 도달할 수 있으면 가장자리에 도달하는 최단 시간을 출력하고, 불을 피해서 가장자리에 도달할 수 없으면 IMPOSSIBLE을 출력한다.

그 과정에서 벽(#)은 사람도, 불도 통과할 수 없다.

알고리즘

• BFS는 4방향으로 퍼지는 불의 움직임과 동일하다.
  
  불은 4방향으로 1칸씩 퍼진다. BFS도 이와 동일하다. BFS로 그래프를 4방향 탐색하는경우, 4방향으로 1칸씩 퍼지며 가중치를 업데이트한다. 따라서 불의 움직임도, 지훈이의 움직임도 전부 BFS로 표현 가능하다.

• 불을 피해서 도달가능한지 어떻게알까?
  지훈이의 위치에서 출발시 도달에 걸리는 시간 < 불의 위치에서 출발시 도달에 걸리는 시간 을 만족하면 된다.

• 가장자리임은 어떻게알까?
  y가 0 || y가 r-1 || x가 0 || x가 c-1 을 만족하면 가장자리인 것이다

• 반례
  

위의 경우 단순히 지훈이의 위치에서 출발시 도달에 걸리는 시간 < 불의 위치에서 출발시 도달에 걸리는 시간 를 적용하면 어떻게될까?

우선 불의 BFS를 거치고나서 벽 안쪽(좌상단) 불에 의한 가중치는 전부 0이다. (벽에 막혀서 불이 방문을 못하니까)

이 상태에서 지훈이의 BFS에서 지훈이의 위치에서 출발시 도달에 걸리는 시간 < 불의 위치에서 출발시 도달에 걸리는 시간를 적용하면 벽 안쪽(좌상단) 부분이 모두 continue 되버리는 문제가 발생한다.

따라서 Fire 의 visited[][]는 매우 큰 수로 초기화 해둬야한다.
-> int INF = 987654321로 초기화하자.

• 풀이 흐름

불의 위치에서 BFS 수행 -> 지훈이가 BFS 수행 (각 방문에서 불보다 먼저 도달 가능한 위치이면 진행, 아니면 continue로 무시) -> 지훈이의 BFS 계속 반복하다가..가장자리 도달하면 비용 출력하고, 못하면 "impossible" 출력

2. 코드

/*

지훈이가 불 보다 가장자리에 빠르게 도착하면됨 ->  bfs각각 돌려서 지훈이의 비용이 더 작은 가장자리 영역 찾으면됨 

지훈이 bfs돌리기
불 bfs돌리기

순회하면서 지훈이쪽이 비용 더 작은거 벡터에 pushback
가장 작은 비용을 출력 

*/
#include <bits/stdc++.h>

using namespace std;


int INF=987654321;
queue<pair<int,int>> q;
int visited_j[1004][1004], visited_f[1004][1004], r, c;
char a[1004][1004];
int dy[4] = {-1,0,1,0};
int dx[4] = {0,1,0,-1};
int ret;

//1:jihoon, 0: fire
void bfs_f() {
	while(q.size()) {
		int y,x;
		tie(y,x)=q.front(); q.pop();
		for(int i=0;i<4;i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if(ny >= r || nx >= c || ny <0 || nx <0 || visited_f[ny][nx]!=INF || a[ny][nx]=='#') continue;
			visited_f[ny][nx]=visited_f[y][x] + 1;
			q.push({ny,nx});
		}	
	}	
}

void bfs_j(int y, int x) {
	visited_j[y][x]=1;
	q.push({y,x});
	while(q.size()) {
		int y,x;
		tie(y,x)=q.front(); q.pop();
		if(y == r-1 || x == c-1 || y == 0 || x == 0) {
			ret = visited_j[y][x];
			break;
		}
		for(int i=0;i<4;i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if(ny >= r || nx >= c || ny <0 || nx <0 || visited_j[ny][nx] || a[ny][nx]=='#') continue;
			if(visited_j[y][x]+1 >= visited_f[ny][nx]) continue;
			visited_j[ny][nx]=visited_j[y][x] + 1;
			q.push({ny,nx});
		}	
	}	
}

int main() {
	pair<int,int> jihoon;
	fill(&visited_f[0][0], &visited_f[0][0]+1004*1004, INF);
	cin >> r >> c;
	for(int i=0;i<r;i++) {
		for(int j=0;j<c;j++) {
			cin >> a[i][j];
			if(a[i][j]=='J') jihoon = {i,j};
			else if(a[i][j]=='F') {
				q.push({i,j});
				visited_f[i][j]=1;
			}
		}
		
	}
	bfs_f();
	bfs_j(jihoon.first, jihoon.second);
	ret == 0 ? cout << "IMPOSSIBLE" : cout << ret;
	return 0;
}

3. 오답 노트

불의 움직임과 BFS

불의 움직임이 BFS의 동작과 동일함을 생각하지 못했다.

BFS는 4방향으로 퍼지며 비용을 업데이트하낟.

반례 생각

처음에 FIRE의 visited[][]를 0으로 초기화했다가 틀렸다.

위의 경우를 생각하지못했다.

로직이 맞는것같은데도 틀리면 이처럼 반례를 떠올려보자

지훈이도, 불도 움직이는데 불을 피해서 도달 가능한지 어떻게확인할까?

핵심은 지훈이의 위치에서 출발시 도달에 걸리는 시간 < 불의 위치에서 출발시 도달에 걸리는 시간 이면 결국 불을 피할수있다는 뜻이다.

이를 확인하기위해서 우선 불에 대해서 bfs돌리고 -> 이후 지훈이에 대해서 bfs돌리며 각 방문마다 위의 조건을 체크해준다.

문제에 주관을 넣지말자.

문제에 불이 하나라는 말이 없다. 불이 하나였으면 좋겠다는 것은 어디까지나 나의 바램이다. 나의 주관을 문제에 넣지말자.
실제로 이 문제도 불이 여러개인 경우가 입력으로 들어오는 문제였다.