BFS - 가중치와 최단거리

13549번: 숨바꼭질 3

백준 숨바꼭질3 문제를 풀다, BFS로 풀었더니 채점에서 11%까지 가고 틀렸습니다 떴다.

왜 그런 것인가 에 대해서 알아보니,

최단 경로를 구할 때(여기서는 걸리는 시간) BFS는 가중치가 없는 경우에 사용한다. 가중치가 없기 때문에 선입선출 FIFO가 적용되어도 되기 때문에 이전 숨바꼭질 문제에서는 사용해도 괜찮은 것이었다.

하지만! 이 문제는 가중치가 0 (순간이동) 또는 1이기 때문에, 일반적인 BFS로 문제를 풀면 틀린답이 나온다.

따라서 가중치(여기서는 걸린시간이 낮은것) 가 높은 순간이동 연산을 먼저 큐에 삽입하면 정답이 나오는 것이다.

bfs를 처음 배울때, 같은 깊이인 노드들을 FIFO로 방문하는 것을 떠올릴 수 있다.

여기서 같은 깊이라는 말이 이 문제에서는 그 깊이가 걸린 시간이고 걸린시간은 가중치라고 볼 수 있다.!