[백준 4179번] 불! - java

문제 설명

1. 미로의 크기 R, C가 주어진다.

2. 불이 나고, 지훈이가 미로안에 있다(지훈이는 한명)

3. 불과 지훈이가 상하좌우로 움직일수 있고 지훈이는 불과 벽을 뛰어넘지 못한다.

4. 지훈이가 미로를 탈출(가장자리 도착)하는 가장 짧은 방법을 구하라.

 

풀이 과정

 1. BFS에 약간의 구현을 더해서 진행하는 문제이다.

 2. 먼저 둘이 동시에 이동한다 가정해보면 코드상에서는 지훈이의 이동보다 불의 이동이 먼저 일어나야 하는데, 

      - 코드에서 지훈이가 불보다 먼저 움직이면 이후에 타죽는다.

      - 불이붙은 지역에 지훈이는 갈 수 없다. 

    그러므로 지훈이를 불보다 늦게 움직이도록 생각한다.

 3. 지훈이는 미로의 가장자리에 있으면 탈출 가능하다. 즉 처음부터 가장자리에 있으면 그냥 탈출하면 된다.

 4. 지훈이는 가장 짧은 루트를 찾는다. 그리고 위의 코드에서 지훈이는 불보다 늦게 움직이므로 한번의 로직에서 이미 지훈이가 이동했던 장소는 불이 번진다고 해도 별 의미가 없다.(어차피 지훈이가 더 빠름)

 5. 지훈이는 벽도 불도 못지나간다. 위치정보를 매번 갱신해주며 '.'만 움직일 수 있다 생각하면 코드가 훨씬 간결해진다.

 6. 불도 마찬가지로 '.'에만 옮겨붙는다고 가정해준다.

 7. 지훈이가 어딘가로 이동했을 때, 그곳에 가장자리면 바로 탈출하면 된다.

 8. BFS가 끝까지 돌았는데 그때까지 탈출 못했으면 IMPOSSIBLE이다.

코드