다익스트라 알고리즘

카카오 미로찾기 문제를 풀다가 최단 경로 알고리즘을 검색 했는데  다익스트라 알고리즘을 발견하여 공부하였다.

(미로찾기 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/81304)

 

---

다익스트라 알고리즘

최단 경로를 구하는 알고리즘으로 우리가 자주 이용하는 네비게이션 기능이 이 알고리즘으로 구성되어 있다고 한다. 그럼 우리가 알고 있는 최단 경로 찾기 방법에 대해서 생각해보면 출발점에서 목적지까지 도착하는 과정의 모든 거리를 더해 어느 길이 가장 짧은 거리가 최단 거리라는 결론을 내리게 된다. 이 과정을 코드로 구현해야한다. 그런데 문제는 모든 길을 전부 탐색하기에는 계산할 수 있는 경우의 수가 너무 많다는 것이다.

 

알고리즘을 생각하기 전에 사람이 최소, 최단이라는 단어가 들어갔을때 가장 우선적으로 확인하는게 뭘까라는 생각을 해보면 지금 탐색 가능한 리스트중 가장 짧은 값을 갖고 있는 방법을 먼저 확인한다. 이 기능이 컴퓨터 안에서는 최소 힙(MIN heap)이라고 한다. 다행히도 Python에는 이 최소 힙 기능을 따로 구현하지 않고 사용할 수 있는 모듈인 heapq가 있었다. 그래서 heapq에 대해서 공부했었다..(https://coco0414.tistory.com/23)

 

여튼 이 모듈을 사용해서 다익스트라 알고리즘을 구현할 것인데 방법은 바로 윗 단락에서 이야기했듯 내가 탐색할 수 있는 리스트 중에서 최소 값을 갖고 있는 길을 찾아서 탐색하는 작업을 반복하고 그 과정중에 길을 찾는다면 그게 최단 거리가 된다. 이렇게 될 수 있는 이유는 이 최소 힙 기능을 이해하면 바로 납득이 가능하다. 최소 힙에서 탐색 종료 시점을 탐색하려는 데이터가 목적지였을때 끝내주면 된다. 즉, 탐색을 했는데 그 값이 목적지까지의 값이더라도 탐색 리스트에 추가하고 그 추가한 데이터고 탐색을 하려했더니 목저지다! 그때 종료해주면 되는 것이다. 그렇게 되면 자연스럽게 목적지까지의 최단거리를 계산할 수 있게 된다.

 

정리하면

1. 경로를 탐색할 탐색리스트를 만든다.

2. 출발지점에 대한 세팅을 하고 탐색리스트에 추가한다.

3. heapq를 통해서 탐색리스트에서 우선 순위가 높은(최소) 데이터를 꺼낸다.

4. 그게 목적지라면 탐색 종료. 아니라면 계속해서 탐색.

 

이게 기본 틀이다. 여기에 조금더 시간을 단축시키기 위해서는 내가 이미 탐색했던 경유지는 다시 탐색할 필요가 없다. 이 부분을 추가해주려면 방문기록 리스트를 만들어서 방문했던 곳에 대한 정보를 넣어주면 된다. 그러면 본격적인 탐색을 시작하기 전에 이 경로를 전에 왔던 적이 있다면 스킵(continue)해주면 된다.

 

예시는 다익스트라 알고리즘 공부에 참고한 블로그에서 가져왔다. (참고 블로그 : https://justkode.kr/algorithm/python-dijkstra)

 

 

코드

import heapq

graph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

distances = {node: float('inf') for node in graph}  # start로 부터의 거리 값을 저장하기 위함
distances['A'] = 0
heap=[]
heapq.heappush(heap, (distances['A'], 'A'))

while heap:  # heap에 남아 있는 노드가 없으면 끝
    print(heap)
    current_distance, current_destination = heapq.heappop(heap)  # 탐색 할 노드, 거리를 가져옴.
    if distances[current_destination] < current_distance:  # 기존에 있는 거리보다 길다면, 볼 필요도 없음
        continue

    for new_destination, new_distance in graph[current_destination].items():
        distance = current_distance + new_distance  # 해당 노드를 거쳐 갈 때 거리
        if distance < distances[new_destination]:  # 알고 있는 거리 보다 작으면 갱신
            distances[new_destination] = distance
            heapq.heappush(heap, [distance, new_destination])  # 다음 인접 거리를 계산 하기 위해 큐에 삽입

코드를 살펴보면

1. graph에는 각 지점과 그 지점에서 갈 수 있는 곳과 거리의 정보를 넣어준다.

2. 각 지점까지의 최소거리 정보를 담을 distances라는 변수에 무한대(inf)값으로 초기화 해주고 시작지점인 'A'지점에 0값을 넣어주고 탐색 리스트에 시작점을 넣어준다.

3. 탐색 리스트에서 우선순위가 가장 높은(최소 값) 장소의 정보를 가져온다.

4. 탐색 리스트에서 가져온 거리(계산된 거리)가 내가 알고 있는 거리보다 길면 그 길은 계속 검색할 필요가 없기 때문에 continue

5. 그렇지 않다면 해당 지점에서 갈 수 있는 길을 item으로 받아와 거리를 계산하고 기존에 알고 있던 거리와 비교해서 짧다면 최단거리 정보를 갖고 잇는 distances에 정보를 담고 다음 탐색리스트에 넣어준다.

 

3~5번 과정을 반복하면 불필요한 거리 계산은 하지 않고 최단거리를 계산할 수 있게 된다. 이 과정을 자세히 보기 위해서 탐색 리스트가 어떤식으로 구성되는지 출력해보았다.

[(0, 'A')]
[[1, 'C'], [8, 'B'], [2, 'D']]
[[2, 'D'], [8, 'B'], [6, 'B']]
[[5, 'E'], [7, 'F'], [6, 'B'], [8, 'B']]
[[6, 'B'], [6, 'F'], [8, 'B'], [7, 'F']]
[[6, 'F'], [7, 'F'], [8, 'B']]
[[7, 'F'], [8, 'B']]
[[8, 'B']]

이 출력 결과에서 봐야할 것은 0번째 인덱스의 값이다. 매번 값이 빠지고 추가 될 때마다 최소 값을 가진 데이터가 0번째 인덱스로 오고 다음 탐색 데이터가 된다는 점이다.

 

최종 결과

{'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 5, 'F': 6}

 

 

다익스트라 알고리즘을 알아봤으니 이제 미로찾기 문제를 풀어야 한다 ㅠ.. 문제 풀이는 다음 포스팅에서..!