특정 지점에서 다른 모든 지점까지의 최단거리를 구하는 알고리즘에서 사용될 수 있습니다.
그러나 가중치의 유무에 따라서는, 반드시 Dijkstra를 사용해야 하는 경우도 있습니다.
가중치란?
비용(cost), 무게(weight) 등 여러 가지 단어로 나타나는, 중요도(우선 순위)를 말합니다.
가중치가 있는 경우에 대한 예시로 경매장을 들 수 있습니다. 경매장에서의 가중치는 가격입니다.
더 늦게 손을 든 사람일지라도 더 높은 가격(중요도가 큰 것)을 제시한 사람이 우선적으로 소유권을 갖습니다.
그러나 반대로, 이미 정해진 같은 가격으로 물건을 파는 타임 세일의 경우 먼저 물건을 집은 사람이
반드시 먼저 사게 됩니다. 이러한 경우에는 가중치가 없다고 말할 수 있습니다.
가중치가 있는 경우
따라서 가중치가 있는 경우에는, 가치에 따라 퇴장 순서가 정해지는 우선순위 큐를 사용해야 합니다.
따라서 Dijkstra Algorithm이 채택됩니다.
가중치가 없는 경우
가중치가 없는 경우에는, 먼저 집은 사람이 먼저 사 가는 FIFO(선입선출)이 적용되어도 되기 때문에
큐를 사용하면 됩니다. 따라서 BFS가 채택됩니다.
물론 Dijkstra로 접근해도 문제를 해결할 수 있습니다.
그러나 두 알고리즘의 시간복잡도를 고려했을 때, BFS로 접근하는 것이 더 효율적임을 쉽게 알 수 있습니다.
백준으로 보는 예시
13549번: 숨바꼭질 3
특정 노드에서 탐색할 수 있는 범위는 *2, +1, -1이며
*2의 가중치가 가장 높고 +1, -1이 동일하게 두 번째로 높은 가중치를 갖습니다.
물론 이 문제는 어떤 순서로 넣느냐에 따라 선입선출로도 답을 도출할 수 있기 때문에 BFS로도
풀이가 가능한 문제이지만, 반대로 말하자면 BFS로 접근하면 삽입 순서에 따라 답이 달라지는 문제입니다.
따라서 순서에 구애받지 않고 가중치(여기서는 걸린 시간)에 따라 꺼내는 우선순위 큐를 이용하는 것이 좋습니다.
5014번: 스타트링크
특정 노드에서 탐색할 수 있는 범위는 +U, -D이며 두 경우 모두 같은 가중치를 갖습니다.
따라서 선입선출로 접근하여도 최단거리를 얻을 수 있는 문제입니다.