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

♣ 데이크스트라 알고리즘

그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘으로, 컴퓨터 과학자 에츠허르 데이크스트라가 고안했다. 

데이크스트라 알고리즘은 변형이 많은데, 원래 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 것이지만 보다 일반적인 변형은 한 꼭짓점을 source 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단 경로를 찾는 최단경로트리 알고리즘이다. 

 

예를 들어 그래프에서 꼭짓점들이 각각 도시를 나타내고, 변들이 도시 사이를 연결하는 도로의 길이를 나타낸다면 데이크스트라 알고리즘을 통해 두 도시 사이의 최단 경로를 찾을 수 있다. 이러한 최단 경로 알고리즘은 네트워크 라우팅 프로토콜에서 널리 이용된다. 

 

 

a와 b 사이의 최단 경로를 찾은 데이크스트라 알고리즘이다. 가장 낮은 값을 가진 방문하지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인접 노드와의 거리를 계산하고, 작을 경우 인접 거리를 업데이트한다. 이 그림에서는 꼭짓점에 도착하면 꼭짓점을 빨간색으로 표시했다. 

 

 

♣ 백준 알고리즘 18352번 문제 이해 

 

 

 

단방향으로 연결된 도시들이 있을 때, 첫 시작 도시 x에서 최단거리가 k인 모든 도시의 번호를 출력하는 문제이다. 최단거리가 k인 도시가 하나도 존재하지 않으면 -1을 출력한다. 도시와 도시 간의 최단 거리를 구하므로 데이크스트라 알고리즘을 사용할 수 있을 것이다. 

 

위의 예제를 보면 X =1 이므로 1번 도시에서 출발해야 하며, 원하는 최단 거리 K = 2 이므로 1번 도시로부터의 최단 거리가 2인 도시를 모두 출력해야 한다. 2번 도시는 1번 도시로부터의 최단 거리가 1, 3번 도시 역시 1번 도시로부터의 최단 거리가 1이다. 4번 도시만이 1->2->4 로 1번 도시로부터의 최단 거리가 2이므로 4가 출력된다. 

 

 

♣ 문제 해결

 

먼저 단방향으로 연결된 도시들을 그래프로 만든다. 단방향으로 연결되어 있으므로 a 도시에만 b를 추가한다. 1은 a 도시에서 b 도시 사이의 거리를 나타낸다. 이렇게 만든 graph를 출력하면 아래와 같다. 

 

 

너비우선탐색에서 해당 노드에 연결된 노드를 추가하는 것처럼 하되, 연결된 노드만이 아니라 연결된 노드까지의 거리를 추가한다. 

 

데이크스트라 함수를 정의한다. distance를 보면 시작 도시로부터 다른 도시까지의 거리를 처음에는 무한대로 설정한다. 

다른 도시로의 최단 거리를 구해야 하므로 무한대로 설정된 값들이 최단 거리 값으로 교체되는 과정을 겪을 것이다. 

시작 도시에서 시작 도시까지의 거리는 0이므로 distances[start] = 0 으로 설정한다. 

 

시작 도시로부터 다른 도시까지의 거리를 탐색하기 위해 que를 정의한다. 이 안에 인접 도시를 하나씩 추가하여 최단 거리를 구한다. 시작 도시 스스로부터 탐색하기 때문에 distance[start]와 0을 que에 넣는다. 

 

아래 예시를 input으로 넣었을 때 

 

시작 도시가 1이므로 distance[1] = 0 이고 이를 que에 넣으면 아래 값이 que에 들어간다. (0이 시작도시에서 시작도시까지의 거리를, 1은 현재 탐색하는 시작도시 1을 의미함)

 

while문을 이용하면 시작 도시에서 접근할 수 있는 모든 노드를 탐색할 수 있다.

dist와 node에는 que의 첫 번째 요소를 pop하여 정한다. dist는 0, node는 1이다. 위에서 확인한 que의 값이 거리와 현재 탐색하는 노드에 해당하도록 들어가는 것이다. 

그런 후 distance의 기존 값(처음에는 무한대임)과 시작 도시와 현재 탐색하는 도시의 거리값을 비교한다. 기존값이 더 작다면 최단거리를 선택해야 하므로 continue를 사용하여 새로운 값을 무시한다. 

 

하지만 새로운 값이 더 작다면 이 새로운 값이 새로운 최단 거리가 되므로, 이 값을 선택한다. 그리고 현재 탐색한 도시를 최단거리로 선택하여 현재 도시와 인접한 도시들까지의 거리를 새롭게 탐색한다. 

 

que가 비어버릴 때까지 while문을 돌리면 제시된 첫 번째 도시로부터 각 도시까지의 최단거리를 구할 수 있다. 

 

 

dijkstra 함수가 종료되면 distances가 리턴된다. 이 리턴값에서 k에 해당하는 거리를 가진 도시를 찾아서 출력한다. k에 해당하는 거리를 가진 도시가 존재한다면 find를 True로 바꾼다. 

 

하지만 k에 해당하는 거리를 가진 도시가 아예 존재하지 않을 수도 있다. 이때는 find가 True로 바뀌지 못하므로 -1을 출력한다. 

 

 

♣ 예제 1이 함수를 거치는 과정

♣ 전체 코드

 

 

♣ 참고 자료

데이크스트라 알고리즘

https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전

 

데이크스트라 알고리즘으로 문제 풀기 

https://star7sss.tistory.com/421

[탐색/다익스트라] 백준 18352 특정 거리의 도시 찾기 - 파이썬(Python)