백준 5427. 불

https://www.acmicpc.net/problem/5427

5427번: 불

 

평범한 bfs를 이용하는 문제인데, 다음 조건을 잘 생각해야 한다. 

불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

 

위 조건에 의해 불이 먼저 이동하고 상근이가 이동한다는 것을 알 수 있다.

또한 불이 언제 퍼지게하는지를 생각해야 하는데, 상근이의 최대 이동 거리를 기억해 놨다가 큐에서 상근이의 위치를 pop해서 빼냈을때 현재까지 이동 거리가, 최대 이동 거리와 다르다면 (크다면) 새로운 깊이의 이동들이 시작되는 것이므로 불을 퍼지게 하면 된다.