[22동계모각코] 7회 계획 및 평가

시작 시간 : 23-01-30 오후 6시

오늘의 목표

• 다익스트라(Dijkstra) 알고리즘 공부

---

이렇게 공부한 알고리즘을 정리해보는 것은 처음이다. 그래서 글이 너무 복잡하고, 정리가 안 되어 있다.

---

오늘은 다익스트라 알고리즘을 공부했다.

다익스트라 알고리즘은 정보 탐색 중에서 최단 경로를 구하기 위한 알고리즘이다.

정보 탐색이란, 탐색에 필요한 정보들을 탐색 전에 미리 알고 있는 경우이다. a에서 b까지의 이동경로를 직접 가보지 않고 미리 알수 있는 경우가 정보탐색인 것이다.

또 다른 특징이 있다면, 비용(cost)의 정보가 모두 음이 아닌 정수여야 한다. 비용 정보가 음수도 포함이 된다면 '플로이드-워셜' 알고리즘으로 해결해야 한댔다.

*논외이긴 하지만 정보가 사전에 준비되지 않은 경우에는 다른 탐색(휴리스틱 탐색 등)을 이용해야 한다.

 

다익스트라 알고리즘은 O(N^2), O(N*log N) 방법이 있다고 한다. 나는 N^2 보다는 N*log N 방법이 더 궁금해 후자를 택했다. 이 방법은 우선순위 큐(priority queue, pq)를 이용하기 때문에 파이썬의 heapq 라이브러리를 가져와야 한다.

---

다익스트라 알고리즘이 무엇인가?

최단경로 알고리즘.

주어진 그래프 중 출발점부터 목적지까지 가야할 때 이때의 최단경로를 구할 수 있다. 말은 최단경로이지만 cost를 무엇으로 두냐에 따라 최소비용, 최단경로 등 다양하게 사용할 수 있다.

 

나는 다익스트라 알고리즘을 이해하기 위해서 거리에 대한 생각보다는 비용의 관점에서 접근했다.

 

출발점(A)부터 종점(D)까지 가는 방법은 여러 방법이 있을 수 있다.

A에서 D로 바로 갈 수 있다면 그 방법과 다른 점(B, C)를 거쳐서 D로 가는 방법도 있다.

그런데 A에서 D로 가는 건 비용(cost)가 많이 들 수도 있어서 B와 C를 통해서 D로 갈 때의 비용도 함께 알아보고 더 저렴한 방법으로 종점으로 가려고 한다.

 

우리는 이런 경우도 고려해야 하기 때문에 최단경로 알고리즘을 써야 한다.

 

출발점에서 갈 수 있는 모든 노드들에 대해 비용을 초기화한다.

그리고 갈 수 있는 모든 노드들 중에서, 비용이 가장 저렴한 노드에서 같은 작업을 한다.

이 작업을 모든 노드들에 대해서 해본다. 그러면 출발점에서 종점까지 가는 최소비용을 알 수 있다.

 

그런데 위 말들을 직접 구현하려니 내 능력이 받쳐주지 못해서 어쩔 수 없이 다른 사람들의 코드를 참고하며 만들었다.

+ 그래프나 코드 뿐만 아니라 본문에서 가르쳐주는 내용 자체도 나름 깔끔하고 잘 알려주고 있다고 생각한다.

그래프, 코드

코드는 다른사람 코드를 참고하니 거의 똑같은 코드가 되어 버려서 많이 아쉬움이 남는다. 그래도 어쩔 수 없다는 생각이다. 나는 python에서 BFS를 구현하는 나만의 방법이 거의 정해져 있는데, 여기까지 시간이 좀 들었던 걸로 기억한다. 마찬가지로 다익스트라도 내 노력과 시간이 해결해 줄 문제라고 생각한다.

---

import heapq

graph = {1: [(2, 2), (3, 5), (4, 1)],
         2: [(3, 3), (4, 2)],
         3: [(2, 3), (6, 5)],
         4: [(3, 3), (5, 1)],
         5: [(3, 1), (6, 2)],
         6: []}

distances = { node : float('inf') for node in graph}
start = 1
distances[start] = 0

visited = set()
queue = []

"""
heapq 라이브러리의 heapq 구조는 최소힙이다. 
그래서 거리가 가장 짧은 곳부터 순회해봐야 하는 다익스트라의 특성상 distance[start]가 list의 앞 원소로 들어가는 것이다.
"""
heapq.heappush(queue, [distances[start], start]) #(노드-목적지)거리와 노드
while queue:
    current_distance, current_destination = heapq.heappop(queue)

    if distances[current_destination] < current_distance or current_destination in visited:
        continue
    visited.add(current_destination) # 방문 체크

    for next_destination, new_distance in graph[current_destination]:
        distance = new_distance + current_distance
        if distance < distances[next_destination]:
            distances[next_destination] = distance
            heapq.heappush(queue, [distances[next_destination], next_destination])

for key in distances:
	print(key, distances[key])

>> 1 0
>> 2 2
>> 3 3
>> 4 1
>> 5 2
>> 6 4

1이 출발점이다. 종점이 만약 [2라면 비용은 2], [4라면 비용은 1]이다.

나는 종점까지 갈 때 최단경로(또는 최소비용)을 알고싶은게 아니라 잘 동작하는지 알고싶었기 때문에 위처럼 코드를 짜두었다.

 

오늘 공부한 내용으로 백준에서 문제를 풀어보았다.