백준 4179 - 불!

🔐 백준 4179 - 불!

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

🔑 풀이

불과 지훈이는 매 분마다 이동하며, 불은 네 방향으로 이동한다. BFS를 이용하여 풀 수 있는

문제로, 처음 문제를 접근했을 때, 큐에 불과 지훈이 중 누구를 먼저 넣을 것인지가 중요하다고 생각했다.

따라서 한쪽으로밖에 삽입을 못하는 queue를 사용하기 보다는 deque를 사용해야 겠다고 생각했다.

문제 조건에서는 둘은 동시에 이동한다고 했지만, queue나 dequq 자료구조의 특성상 하나씩 빼서

BFS를 돌릴 수 밖에 없고, 처음에는 불보다 지훈이를 먼저 BFS를 돌리는게 맞다고 생각했다.

하지만, 당연히 틀리게 되었고 지훈이와 불이 동시에 도착하는 칸에는 갈 수 없기 때문에 불을 먼저

큐에 넣는게 맞다는 것을 알게 되었다. 그 이후는 조건에 맞게 BFS 알고리즘을 사용하면 된다.

다른 사람의 풀이를 살펴보고 나서, 지훈이와 불에 대해 각각의 BFS를 사용하여 그 둘을 비교하여

답을 찾아내는 방법도 있다는 것을 알게 되었다. 이렇게 풀면 복잡하게 조건문을 사용하지 않아도 되어

좋은 것 같다.

🧩코드

• 미로의 각 칸을 입력받을 때, 어느 위치에 불과 지훈이가 위치할지 모르기 때문에, 큐에 넣는 순서를
  위해 STL deque 자료구조를 사용하여 불은 push_front, 지훈이는 push_back을 사용하였다.

• 덱에서 원소를 꺼내고, 지훈이인지 확인한 후 미로의 가장자리에 있는지를 먼저 확인해 준다.

• 미로에서 벽(#)과 불(F)은 거리 배열의 값은 -1, 지훈(J) 은 1, 지날 수 있는 공간(.)은 0이다.

• DFS에서 거리가 0인 경우 에 대해서만 J, F 값에 따라 처리해 주었다.