[코딩테스트 Python3 (8)] Dijkstra 다익스트라

Queue vs. Priority Queue

Queue : 선입선출(First In First Out)

Priority Queue : 우선순위가 가장 높은 값이 먼저 추출

→ 완전이진트리 구조의 Heap으로 구현

완전이진트리로 구현하면, 시간복잡도 enqueue: O(logN), dequeue: O(logN)

 

Heap 자료구조

완전 이진 트리(complete binary tree) 형태의 자료구조

→ 완전 이진트리의 특성으로 인해서 트리구조(노드)가 아닌 리스트로도 구현이 가능하다. 

형제 노드 사이에서는 값의 크기가 중요하지 않다.

 

Heapify

min_heap 만들기

import heapq

min_heap = [5, 3, 9, 4, 1, 2, 6]
heapq.heapify(min_heap) -> O(N)
#dequeue(우선 순위가 가장 높은 노드를 가져올 수 있다) -> O(logN)
heapq.heappop(min_heap)
#enqueue -> O(logN)
heapq.heappush(min_heap, 1)

max_heap 만들기(min_heap에서 변형하기)

import heapq

max_heap = [5,3,9,4,1,2,6]
max_heap = [(-1 * i, i) for i in max_heap]
heapq._heapify_max(max_heap)
weight, value = heapq.heappop(max_heap)

 

Dijkstra 다익스트라

시작점에서 도착점으로 가는 경로 중 가장 비용이 적게 드는 경로를 구하시오? 라는 문제에서

• 비가중치 그래프의 경우 BFS
• 가중치 그래프의 경우 Dijkstra

가중치 그래프에서 시작점과 도착점이 주어졌을 때, 최단 경로(shortest path)를 return하는 알고리즘

방문할 수 있는 노드 중에 가장 비용이 작은 곳을 방문하는 것(우선순위가 높은 곳 방문)

시간 복잡도 O(ElogE)

 

가중치 그래프

(노드, 가중치)로 표현해야 함

def dijkstra(graph, start, final):
	costs = {}
    pq = [] #priority queue
    heapq.heappush(pq, (0, start))
    
    while pq:
    	cur_cost, cur_v = heapq.heappop(pq)
        if cur_v not in costs:
        	costs[cur_v] = cur_cost
            for cost, next_v in graph[cur_v]:
            	next_cost = cur_cost + cost
                heapq.heappush(pq, (next_cost, next_v))
    return costs[final]
    
graph = {...}
dijkstra(graph, 1, 8)

https://leetcode.com/problems/network-delay-time/

Network Delay Time - LeetCode

def networkDelayTime(times, n, k)
	#dict의 원소로 list를 사용할 것이기 때문에 아래와 같이 선언
	graph = defaultdict(list)
    for time in times:
    	graph[time[0]].append((time[2], time[1]))
    
    costs = {}
    pq = []
    heapq.heappush(pq, (0, k))
    
    while pq:
    	cur_cost, cur_node = heapq.heappop(pq)
        if cur_node not in costs:
        	costs[cur_node] = cur_cost
            for cost, next_node in graph[cur_node]:
            	next_cost = cur_cost + cost
                heapq.heappush(pq, (next_cost, next_node))
    
    #방문하지 않은 node가 있는지 확인하는 코드
    for node in range(1,n+1):
    	if node not in costs:
        	return -1
            
    return max(costs.values())    
    
    
input : times = [[2,1,2],[2,3,5],[2,4,1],[4,3,3]], n=4, k=2
output : 4