데이크스트라 알고리즘(백준 알고리즘 13549번)

♣ 데이크스트라 알고리즘

한 꼭짓점을 source 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단 경로를 찾는 최단경로트리 알고리즘을 데이크스트라 알고리즘이라고 한다. 아래 정리한 내용을 참고할 수 있다. 

 

https://jy-deeplearning.tistory.com/86

Dijkstra(데이크스트라 알고리즘, 백준 알고리즘 18352번)

 

 

♣ 백준 알고리즘 13549번(숨바꼭질3) 이해

 

위 문제는 수빈이의 위치에서 어떤 경로로 이동해야 가장 빠르게 동생을 찾을 수 있는지 찾는 문제이다. 수빈이는 걸어가거나 순간이동을 할 수 있는데, 걸어가면 현재 위치의 -1, 또는 +1 위치로 옮겨갈 수 있으며 가는 데 1초의 시간이 걸린다. 순간이동을 하면 현재 위치*2 의 위치로 갈 수 있으며 가는 데 0초의 시간이 걸린다. 예를 들어 수빈이의 위치를 5, 동생의 위치를 17이라고 하면 5 - 순간이동(0초) - 10 - (-1칸 걷기, 1초) - 9 - 순간이동(0초) - 18 - (-1칸 걷기, 1초) - 17 이 최단 시간으로, 동생을 찾는 데 총 2초가 걸린다. 

 

주의할 점은, 수빈이와 동생의 위치가 0보다 크거나 같고, 100000보다는 작거나 같다는 점이다. 또한 수빈이가 항상 동생 뒤에 있는 것은 아니다. 예를 들어서 수빈이의 위치는 999, 동생의 위치는 1일 수도 있다. 

 

 

♣ 백준 알고리즘 13549번(숨바꼭질3) 풀이

이 문제는 수빈이의 위치와 동생의 위치를 마치 그래프의 한 점인 것처럼 생각하면 데이크스트라 알고리즘으로 해결할 수 있다. 수빈이의 위치가 node 5, 동생의 위치가 node 17인 것처럼 생각하고, node5에서 node17로 갈 수 있는 최단 시간을 구하는 것이다. 이때, 걸리는 시간을 node 사이의 거리로 바꿔서 생각하면 수빈이가 위치한 node에서 동생이 위치한 node로 가는 최단거리를 찾으면 된다. 

 

풀이 아이디어는 다음과 같다. 

 

1. 수빈이의 위치를 start node로 정하고, 이 노드부터 탐색을 시작한다. 

2. 탐색할 다음 노드는 조건에 맞게 현재노드-1, 현재노드+1, 현재노드*2 이다. 

3. 탐색할 다음 노드를 que에 추가해가며 최단 거리를 찾는다. 

4. 탐색할 노드가 목표 노드(동생의 위치)와 같다면 탐색을 종료한다. 

 

우선 시작하는 노드로부터 모든 노드로의 거리를 무한대로 설정한다. 그리고 시작하는 노드에서 시작하는 노드까지의 거리는 0이므로 distances[start] = 0 으로 설정한다. 앞으로 탐색할 노드를 담을 que를 정의하고, 이 안에 시작 노드와 시작노드까지의 거리를 넣는다. 

 

 

이제 que를 탐색한다. que의 첫 요소를 heappop으로 가져온다. 이때의 node가 동생이 위치한 노드, 즉 탐색 목표인 노드이면 이미 이 노드까지를 탐색한 것이므로 distances를 return하면서 탐색을 종료한다. 

 

그렇지 않다면 현재 노드에서 갈 수 있는 세 가지 노드를 탐색한다. node-1, node+1, node*2 세 가지 노드이다. 각 노드까지의 거리(가는 데 걸리는 시간)는 각각 1, 1, 0이다. 

 

for문을 이용하여 세 가지 노드를 탐색하는데, 만약 탐색하는 노드가 가장 큰 노드보다 크거나, 0보다 작아지면 그 노드는 존재하지 않으므로 탐색하지 않는다. 탐색할 수 있는 노드인 경우, 시작노드로부터 현재 탐색 노드까지의 거리(distance)가 원래 주어져 있던 거리(distances[next_node])보다 짧으면 짧은 거리로 주어져 있던 거리를 대체한다. 

 

탐색이 끝난 노드는 que 안에 넣어서 이 노드와 연결된 다음 노드를 탐색하도록 한다. 

 

♣ 백준 알고리즘 13549번(숨바꼭질3) 전체 코드