[ 이것이 코딩테스트다 ] 26일차

안영우·2021년 2월 1일

나동빈 코딩테스트

[ 이것이 취업을 위한 코딩 테스트다. with 파이썬 ]

목록 보기

26/39

✏️ 서론

오늘은 저번시간에 배웠던 dijkstra_algorithm(linear_path)에 이은 개선된 dijkstra_algorithm을 배워보자.

✏️ 본론

간단한 dijkstra_algorithm은 최단 거리가 가장 짧은 노드를 찾기 위해 매번 최단거리 테이블을 선형적으로(모든 원소를 앞에서부터 하나씩) 탐색해야했다.
선형적으로 탐색한 코드는 다음과 같다.

for i in range(1, n+1):
    if distance[i] < min_value and not visited[i]:
        min_value = distance[i]
        index = i
return index

📍 heap을 이용한 다익스트라 알고리즘

개선된 다익스트라 알고리즘에서는 기본적으로 힙(heap)자료구조를 이용한다.
힙(Heap)자료구조를 이용하게 되면 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아 처리하므로 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있다.

⚡️ heap이란?

힙 자료구조는 우선순위(priority_queue)를 구현하기 위해 사용하는 자료구조 중 하나다.
우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징인데, 표로 나타내면 다음과 같다.

자료구조	추출되는 데이터
스택(stack)	가장 나중에 삽입된 데이터
큐(queue)	가장 먼저 삽입된 데이터
우선순위 큐(priority_queue)	가장 우선순위가 높은 데이터

우선순위 큐를 구현할 때는 내부적으로 최소 힙(min_heap) 혹은 최대 힙(max_heap)을 이용한다. 최소 힙을 이용할때는 값이 가장 낮은 데이터가 먼저 삭제되며, 최대 힙은 값이 큰 데이터가 가장 먼저 삭제됨을 알아두자.

파이썬에서 우선순위 큐 라이브러리를 사용할때는 default값이 최소 최소 힙(min_heap)으로 설정되어있는데, 최대 힙(max_heap)으로 사용하고 싶다면, 값에 음수 부호(-)를 붙여서 넣었다가 heapq.heappop 할 때 다시 음수 부호(-)를 붙여 원래의 값으로 돌리면 된다.

# desc heap_example
def heapsort(n):
    h = []
    result = []

    for i in n:
        heapq.heappush(h, -i)

    for i in range(len(h)):
        result.append(-heapq.heappop(h))

    return result

우선순위를 구현방식의 시간복잡도는 다음과 같다.
| 우선순위 큐 구현방식 | 삽입 시간 | 삭제 시간 |
| :----: | :----: | :----: | :----: |
| 리스트(list) | O(1) | O(1) |
| 힙(heap) | O(logN) | O(logN) |

데이터의 개수가 N개 일때, 힙 자료구조에 N개의 데이터를 모두 넣은 뒤에 다시 모든 데이터를 꺼낸다고 가정하면 전체 연산 횟수는 대략 2NlogN으로 빅오표기법에 따라서 O(NlogN)이 될 것이다.

다시 본론으로 돌아와 단계별로 우선순위 큐가 어떻게 변화하는지 알아보자.
글로만 봤을 때 이해가 잘 되지않아 강의를 찾아봤는데, 궁금하다면 들어보자!

이코테

힙 정렬강의

linear_path와의 주요 차이점은 방문처리해주는 함수(get_smallest_node())가 없고 대신 우선순위 큐를 이용하는 방식으로 대체할 수 있기 때문에 코드가 간결해진다.

'''
6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2
'''

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())
start = int(input())
graph = [[] for _ in range(n+1)]
distance = [INF] * (n+1)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue

        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF:
        print('infinity')
    else:
        print(distance[i], end=' ')
👉🏽 0 2 3 1 2 4