백준 4179. 불!

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

4179번: 불!

 

bfs 를 이용해 풀면 된다.

 

문제에서 명시는 안되어 있지만 예제를 보면 지훈이가 먼저 이동하고 그 후에 불이 퍼지는것을 알 수 있다. 

따라서 bfs를 돌리기 위한 큐에 지훈이의 위치를 먼저 넣어주고, 그 후에 불들의 위치를 넣어준다.

이렇게 하면 자연스럽게 지훈이가 먼저 이동하고 불들이 퍼질 것이다.

그리고 맵에 지훈이가 있는 위치는 'J'로 불이 있는 위치는 'F'로 표시해준다. 

 

큐에서 좌표를 뺐을때 해당 좌표의 맵이 지훈이라면 다음 위치를 탐색하고 현재 위치는 '.' 즉 빈 공간으로 만들어준다. 

(지훈이는 이동하기 때문) 

다음 위치가 맵을 벗어난다면 탈출한것이다. 

 

큐에서 좌표를 뺐을때 해당 좌표의 맵이 불이라면 불들이 번지게 하면 된다.

이때 불들이 이동할때도 다음 좌표가 불이라면 이동시키지 않는다. (이미 방문했기 때문) 

 

 

보통 bfs는 방문한 곳을 기억하도록 visited 배열을 만들어 다시 방문하지 않도록 하는데, 이 문제의 경우 어처피 불이 번진곳은 지훈이가 이동하지 못하기 때문에 필요없을 것 이라고 생각했다.

그런데 시간초과를 받아서 지훈이가 방문한 배열 visited를 만들었더니 통과했다.

생각해보면 맵이 1000x1000으로 넓기 때문에 불이 충분히 퍼지기 전까지 지훈이의 중복된 움직임이 엄청 많기 때문에 역시 visited 배열이 필요하긴 하다.