[이것이 코딩테스트다] p.240 우선 순위 큐

우선순위 큐 : 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징.

 

추출되는 데이터

 

스택 : 가장 나중에 삽입된 데이터

큐 : 가장 먼저 삽입된 데이터

우선순위 큐 : 가장 우선순위가 높은 데이터

 

이러한 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다.

예를 들어 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인해야 하는 경우를 가정

-> 우선순위 큐 자료구조를 이용하면 효과적임

 

우선순위 값을 표현할 때는 일반적으로 정수형 자료형의 변수가 사용됨.

물건 정보 -> 물건의 가치, 물건의 무게로만 구성된다면 모든 물건 데이터를 (가치, 물건)으로 묶어서 우선순위 큐 자료구조에 넣을 수 있는 것.

 

물건을 꺼내게 되면, 항상 가치가 높은 물건이 먼저 나오게 됨.

데이터가 (가치,물건)으로 구성된다면 '가치' 값이 우선순위 값이 되는 것.

우선순위 큐를 구현할 때는 내부적으로 최소 힙, 최대 힙을 이용한다.

 

최소 힙을 사용하는 경우 '값이 낮은 데이터가 먼저 삭제' 되며,

최대 힙을 사용하는 경우 '값이 큰 데이터가 먼저 삭제' 된다.

 

기본적으로 최소 힙 구조를 이용하며, 다익스트라 최단 경로 알고리즘에서는 비용이 적은 노드를 우선하여 방문하므로 최소 힙 구조를 기반으로 하는 파이썬의 우선순위 큐 라이브러리를 그대로 사용하면 적합하다.

 

 

또한 최소 힙을 최대 힙처럼 사용하기 위해서 일부러 우선순위에 해당하는 값이 음수 부호를 붙여서 넣었다가 다시 꺼낸 다음에 음수 부호를 붙여서 원래의 값으로 돌리는 방식또한 있다. 자주 사용된다.

 

 

리스트는 삽입 시간 1, 삭제시간 O(N)

힙은 삽입 시간 O(logN), 삭제시간 O(logN)

데이터의 개수가 N개일 때, 힙 자료구조에 N개의 데이터를 모두 넣은 뒤에 다시 모든 데이터를 꺼낸다고 해보자.

삽입을 N번 반복하니 O(NlogN)이고 삭제할 때도 N번 반복하므로 O(NlogN)이다. 

 

대부분 힙을 이용했을 때 훨씬 빠르게 동작한다.

모든 원소를 저장한 뒤에 우선순위에 맞게 빠르게 뽑아낼 수 있으므로 힙은 '우선순위 큐'를 구현하는데 가장 많이 사용된다.

 

현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐를 추가로 이용한다고 하자.

시작 노드 부터 (노드 번호, 거리) 순서대로 튜플 형태로 우선순위 큐에 넣는다.

거리가 가장 짧은 노드를 선택하기 위해서는 우선순위 큐에서 그냥 노드를 꺼내면 된다.

기본적으로 거리가 짧은 원소가 우선순위 큐의 최상위 원소로 위치해 있다.

 

따라서 우선순위 큐에서 노드를 꺼낸 뒤에 해당 노드를 이미 처리한 적이 있다면 무시하면 되고, 아직 처리하지 않은 노드에 대해서만 처리하면 된다.

 

노드를 기준으로 더 짧은 경로를 찼았다면 그 짧은 경로를 각각 갱신하면 된다.

더 짧은 경로를 찾은 노드 정보는 우선순위 큐에 넣는다.

 

이어서 우선순위 큐에서 원소를 다시 꺼내서 동일한 과정을 반복한다.

가장 거리가 짧은 노드 원소 추출 -> 그 원소 주변 값 최소 거리로 갱신 -> 해당 노드 처리 형태로 변경 -> 반복.

 

모든 단계를 거친 후에 최단 거리 테이블에 남아 있는 0,2,3,1,2,4 가 각 노드로의 최단 거리이다.

가장 짧은 노드를 찾기 위해서 우선순위 큐를 이용하고 있으며, 훨씬 빠르게 동작한다.

 

최단 거리가 가장 짧은 노드를 선택하는 과정을 다익스트라 최단 경로 함수 안에서 우선순위 큐를 이용하는 방식으로 대체

9-2.py 개선된 다익스트라 알고리즘 소스코드

import heapq
import sys

input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n+1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (N+1)

# 모든 간선 정보를 입력받기
for _ in range(m):
    a,b,c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 C라는 의미
    graph[a].append((b,c))

def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
    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):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    #도달 할 수 있는 경우 거리를 출력
    else:
        print(distance[i])