백준 1753번: 최단경로

✔ 풀이를 위한 아이디어

• 그래프 (Graph) 이론
• 다익스트라 (Dijkstra) 알고리즘 (한 지점에서 다른 모든 지점까지의 최단 경로)
  
  

✔ 알고리즘 설명

다익스트라 알고리즘을 공부한 뒤에 코드를 짜보았다.
https://www.youtube.com/watch?v=F-tkqjUiik0 의 알고리즘 설명부분만 참고하였다.

필요한 데이터 목록

• 노드와 간선 정보가 담긴 그래프 (각 노드에 연결된 지점들과 그에 대응하는 거리 정보)

graph = [[] for _ in range(V+1)]
for _ in range(E):
    u, v, w = map(int, sys.stdin.readline().split())
    graph[u].append((w, v))  # graph[u]에 index 0이 거리, 1이 지점인 tuple이 여러 개 달려있음

• 각 지점까지의 최소 거리에 대한 정보가 담긴 테이블 (모두 무한 값으로 초기화)

table = [INF]*(V+1)

• 방문하지 않은 노드 중에서, 최단거리가 가장 짧은 노드를 반환하는 우선순위 큐 (최소 힙)
  우선순위 큐 사용 안 할 때는 시간복잡도가 O(N), 사용 할 때는 O(logN) <- 사용 해야함

table[start] = 0  # 시작점의 table은 0으로 초기화 (나부터 나까지의 거리는 0이므로)
heap = [(table[start], start)] 
# heap에도 역시 index 0이 거리, 1이 지점인 tuple이 여러 개 달려 있음
# table 정보를 갱신할 때마다 heap에 넣어줌 (갱신한 지점과, 현재의 그 지점까지의 최소 거리) 

핵심 알고리즘

def dijkstra():

    while heap:
        tmp = heapq.heappop(heap)  # (거리, 지점) tuple로 구성된 현재 처리 중인 노드 정보

        if table[tmp[1]] < tmp[0]:  # 이미 있는 값이 더 작다면, 갱신 완료 한 것이므로 건너 뜀
            continue   		    # (5, 3) -> (4, 3) 순서로 들어가도 (4, 3) 이 먼저 나와서 남은 것

        for i in range(len(graph[tmp[1]])):  # graph 뒤에 달려 있는 tuple의 개수만큼 반복
        				     # 현재 탐색 중인 노드와 연결된 지점들을 검토
                             
            current = graph[tmp[1]][i]  # 현재 탐색 중인 노드와 연결된 지점들 중
            				  현재 다음 지점으로 고려 중인 노드에 대한 정보가 담긴 tuple
           				# current는 갈 지점에 대한 정보, tmp는 현재 지점에 대한 정보

            if table[tmp[1]] + current[0] < table[current[1]]:
                # table[tmp[1]]: 기존에 시작 노드 ~ 현재 탐색 중인 노드 까지의 최소 거리
                # current[0]: 현재 탐색 중인 노드 ~ 다음 지점으로 고려 중인 노드 까지의 거리
                # table[current[1]]: 기존에 시작 노드 ~ 다음 지점으로 고려 중인 노드 까지의 최소 거리
               
                table[current[1]] = table[tmp[1]] + current[0]
                heapq.heappush(heap, (table[current[1]], current[1]))
	

• 알고리즘은 아래와 같은 순서로 동작한다.

1. 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택 해서 처리 시작

2. 해당 노드와 연결 된 지점들을 모두 검토하며, 해당 노드를 거쳐 다른 노드로 가는 거리를 확인하고, 기존의 최단 거리 테이블을 갱신함.

3. 테이블을 갱신할 때마다 그 다른 노드에 대한 정보를 힙에 넣어 줌

4. 위의 1~3 과정을 반복하며 모든 테이블을 갱신해나간다.

✔ 전체 코드

import sys
import heapq

INF = float('inf')  # 무한을 INF로 정의

V, E = map(int, sys.stdin.readline().split())
start = int(input())

graph = [[] for _ in range(V+1)]
for _ in range(E):
    u, v, w = map(int, sys.stdin.readline().split())
    graph[u].append((w, v)) 

table = [INF]*(V+1)

table[start] = 0 
heap = [(0, start)] 


def dijkstra():

    while heap:
        tmp = heapq.heappop(heap)

        if table[tmp[1]] < tmp[0]: 
            continue

        for i in range(len(graph[tmp[1]])): 
            current = graph[tmp[1]][i]  

            if table[tmp[1]] + current[0] < table[current[1]]:
                table[current[1]] = table[tmp[1]] + current[0]
                heapq.heappush(heap, (table[current[1]], current[1]))


dijkstra()

for i in range(1, V+1):
    if table[i] == INF:  # Python에서 전역 변수로 선언된 리스트는 global 안써도 값이 변함
        print("INF")     # https://livlikwav.github.io/python/python-mutable-and-namespace/
    else:
        print(table[i])

꽤나 복잡한 알고리즘이기 때문에 계속 복습하고, 다시 구현해보도록 하자!

• 백준 11779번: 최소비용 구하기 2 - http://boj.kr/280a4ba8af124dea929fe90e7fa82f84
  위 문제를 풀면서, 다익스트라 코드 자체가 더 깔끔해진 것 같아서 첨부한다.