1753-백준-최단경로

1. 문제 출처

https://www.acmicpc.net/problem/1753

1753번: 최단경로

2. 풀이

데이크스트라를 사용하는 문제이다.

데이크스트라 알고리즘은 별로 사용한 적이 없어서 많이 해멘던 것 같다.

 

그래프 자료 구조를 사용하여 weights ,node,  edge  를 구현 하였고 해당 구조를 사용하여 데이크스트라 알고리즘 을 사용하기 위해 우선순위큐를 구현해야 했다.  이 우선순위 큐를 구현하기 위해 heap 구조를 사용하였다.

heap을 사용하지 않고 그냥 리스트 또는 정렬된 리스트를 사용했을 경우 정렬 또는 삭제시 시간 복잡도가 O(N) 이 되기 때문에 두가지 모두 시간 복잡도가 O(logN)인 heap을 사용하였다...

import heapq

# input 을 sys.stdin.readline으로 대체
import sys
input = sys.stdin.readline

# 입력
n, m = map(int, input().split())
start = int(input())
graph = [[] for _ in range(n+1) ]
weights = [float('INF')]*(n+1)

# 간선 정보 입력 받기 
for _ in range(m):
    start_node,end_node,weight = map(int,input().split())
    # start_node -> end_node 의 가중치가 weight
    graph[start_node].append([end_node,weight])
    
    
def dijkstra(start):
    # 우선순위 큐를 구현하기 위하여 heap 구조를 사용한다. 
    q = []
    # 시작점에서 시작점으로 가는 최간 경로는 0이므로 0,start를 넣는다.
    heapq.heappush(q , [0,start])
    weights[start] = 0
    # q가 빌때까지 반복한다.
    while q:
        #min_heap 에서 pop을 하게 되면 가장 작은 값을 꺼내게 된다. (weight, node)
        weight, now = heapq.heappop(q)
        
        # now 가 이미 처리된 노드라면 continue
        if weights[now] < weight:
            continue
        # graph 에서 해당 노드와 인전한 노드와 거리 불러오기
        for node,w in graph[now]:
            # 만약 해당 노드를 들려서가는 것이
            cost = w +weight
            # 그냥 가는 것보다 가중치가 작다면
            # 해당 가중치로 초기화 해준다.
            if cost < weights[node]:
                weights[node] = cost
                # 그리고 우선순위 큐에 추가한다.
                heapq.heappush(q,[cost, node])
        
dijkstra(start)

for i in range(1,n+1):
    if weights[i] == float('inf'):
        print('INF')
    else:
        print(weights[i])