[백준] 1753번번 (python 파이썬)

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

다익스트라 알고리즘이다.

다익스트라 알고리즘은 edge의 가중치가 양수만 있을때 사용할 수 있다.

 

2가지 방법으로 풀 수 있다.

1. 해당 노드에서 이어진 노드들중 가중치가 가장 작은 경로를 선택한다.

2. 우선순위 큐를 사용하여 해결할 수 있다.

 

우선순위 큐를 이용하여 풀었다. (가장 작은 가중치를 선택해야함)

파이썬에서는 우선순위 큐를 사용하기위해 heapq를 사용할 수 있다. (동작은 min heap인듯 하다)

 

다익스트라를 풀기위해 필요한 것들

1. 우선순위 큐에 사용될 list ( queue = list() )

2. 가중치를 저장할 list ( distance = list() )

 

세팅

distance[시작점] = 0

우선순위 큐에 (해당 점의 가중치, 해당점) 을 넣는다.

 

queue가 빌때까지 반복

1. queue에서 pop을 한다.( min heap으로 이루어진 우선순위 큐이기때문에 가장 작은 가중치가 나옴)

   pop한 가중치, pop한 점 2개가 나온다. ( 현재 노드임 )

 

2. distance[pop한 점]가 pop한 가중치 보다 작다면 1번으로 돌아간다. (이미 작기 때문에 볼 필요가 없다.)

 

3. pop한 노드 ( 현재 노드 ) 에서 이어진 노드들을 확인한다.

   이어진 노드로 가는 가중치와 현재 노드의 가중치를 더한 값이 distance[이어진 노드] 작다면 distance[이어진 노드]를     계산된 가중치로 바꿔주고 이어진 노드들을 우선순위 큐에 넣는다. 

 

import math
import heapq
import sys

input = sys.stdin.readline

v, e = map(int, input().split())
k = int(input())  # 시작점
dist = [math.inf] * (v + 1)  # 거리 테이블
heap = []
graph = [[] for _ in range(v + 1)]

for _ in range(e):  # 그래프 초기하
    start, end, w = map(int, input().split())
    graph[start].append((w, end))


def dijkstra(start):
    dist[start] = 0  # 시작 가중치 = 0
    heapq.heappush(heap, (dist[start], start))  # 시작점 우선순위 큐에 넣음 (가중치가 맨앞으로)

    while heap:  # 큐에 아무것도 없을때 까지
        current_weight, current = heapq.heappop(heap)  # 큐에서 가장 작은 거리 pop

        if dist[current] < current_weight:  # pop한 노드의 가중치가 이미 저장된 가중치보다 크면 패스
            continue

        for graph_next_weight, next in graph[current]:
            next_weight = current_weight + graph_next_weight  # 이전 노드에서 다음 노드로 가느 가중치

            if next_weight < dist[next]:  # 계산된 가중치 < 다음 노드의 가중치
                dist[next] = next_weight
                heapq.heappush(heap, (next_weight, next))  # 큐에 다음 노드랑 게산된 가중치 넣음


dijkstra(k)
for i in range(1, v + 1):
    if dist[i] == math.inf:
        print("INF")
    else:
        print(dist[i])