[Python] 백준 1753번 문제, 최단경로

<문제 링크>

 

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

1753번: 최단경로

 

---

<풀이>

 

다익스트라 알고리즘을 사용해 최단 경로를 구하는 문제이다.

그런데 리스트를 사용한 다익스트라 알고리즘은 모든 정점에 대해 모든 경우를 처음부터 탐색해야 하기 때문에 비효율적이라고 한다.

그래서 우선순위 큐를 이용한다면 최소한으로 모든 경우의 최단 경로를 업데이트 할 수 있다.

이 우선순위 큐는 min_path를 업데이트 했을 때만 push가 되며, 최소힙으로 정렬된다.

 

heapq을 이용한다면 최소힙같이 값이 들어가며, 나는 (가중치, 노드)와 같이 값을 넣었는데 heapq은 튜플도 0번째 인덱스를 기준으로 정렬된다고 한다.

그래서 가중치 우선순위 큐를 이용해 빠르게 최단 경로를 업데이트했다.

 

연산은 우선순위 큐가 비어 있을 때까지 진행되며, 비어 있지 않다면 0번째 인덱스를 포커싱한다.

현재 가중치가 가장 낮은 선이 (5, 4)이고 min_path[4]가 3이라면, 현재 포커싱 중인 4로 가는 가중치가 기존 최소값보다 크기 때문에 continue해서 업데이트 하지 않고 빠르게 다음으로 넘어간다.

 

그렇지 않고 (1, 4)이라면 3 < 1은 False이기 때문에 현재 정점을 기준으로 업데이트가 이루어진다.

그래서 4에서 출발하는 간선들의 정보를 가져와 sum을 구한 다음에 처음 호출 당하거나 기존 min_path[]보다 최단 경로일 경우에 min_path를 sum으로 업데이트한 다음에 우선순위 큐에 넣어준다.

 

그런 다음에 출력을 할 때 min_path가 -1이라면 경로가 없는 것이기 때문에 "INF"를 출력하고 -1이 아니라면, min_path 값을 출력해주면 된다.

 

---

<코드>

graph[][]: 그래프 정보

min_path[]: 각 정점 별 최단 경로

que[]: 우선순위 큐

---

import heapq
import sys

def logic(K):
    que = [] # 우선순위 큐 -> (가중치, 노드)를 담고 가중치 기준으로 정렬

    heapq.heappush(que, (0, K)) # 큐에 시작노드((0, K)) 삽입
    min_path[K] = 0 # 시작점은 최단 경로 0

    while que:
        distance, focus = heapq.heappop(que) # 가중치가 가장 짧은 노드 정보 가져오기

        # 이미 최소값이 설정된 노드이면 탐색하지 않음
        if (min_path[focus] < distance) and (min_path[focus] > -1):
            continue

        # 연결된 노드(focus)를 거쳐 지나가는 최단 경로들 갱신하기
        for i in graph[focus]:
            sum = distance + i[1] # 누적 가중치

            # 현재보다 최단 경로거나 처음 호출된 것이라면 최단 거리 갱신
            if (sum < min_path[i[0]]) or (min_path[i[0]] == -1):
                min_path[i[0]] = sum
                heapq.heappush(que, (sum, i[0]))

if __name__ == "__main__":
    V, E = map(int, sys.stdin.readline().split())
    K = int(sys.stdin.readline())

    graph = [[] for _ in range(V+1)]
    min_path = [-1] * (V+1)

    # input
    for i in range(E):
        u, v, w = map(int, sys.stdin.readline().split())

        graph[u].append([v, w])

    # logic
    logic(K)

    # print
    for i in range(1, V+1):
        if min_path[i] == -1:
            print("INF")
        else:
            print(min_path[i])