[알고리즘/백준] 1753번 최단경로 Python 파이썬

 

이번 문제는 처음으로 heap 을 사용해보고 푸는데 애 먹었던 문제였습니다.

 

 

문제는 보기에 간단해보입니다. 시작점이 주어졌을때 각 정점의 최소 경로 거리를 구해서 출력하는 문제입니다. 저는 처음에 탐색 문제로 판단하고 BFS를 통해서 풀려고 접근했습니다 풀다가 너무 복잡해진게 틀린 거 같아서 다른 분의 풀이를 찾아보니 다들 heap을 사용하시더라고요 

 

그래서 왜 heap을 사용해서 푸는 가? 의문이 생겼는데 해당 블로그 https://my-coding-notes.tistory.com/200 이해할 수 있었습니다. 간단히 말하면 효율성 때문에 heap을 써주는 것이었습니다. heap의 특징으로는 최소값을 먼저 pop 해주는데 이를 통해서 최소 경로를 구하는데 계산을 단축할 수 있게 됩니다. 

 

아래와 같은 코드로 통과하였습니다.

 

import sys
import heapq
input = sys.stdin.readline
INF = 100000000

v, e = map(int, input().split())
k = int(input())
to_list = [[] for _ in range(v+1)]
distance = [INF]*(v+1)
queue = []

for i in range(e):
    u, v1, w = map(int, input().split())
    to_list[u].append([v1,w])

def dijkstra(s):
    distance[s] = 0 # 자기 자신
    heapq.heappush(queue, [0, s]) # 시작값을 0
    while queue: # heappop 작은 값을 먼저 꺼냄
        curw, curn = heapq.heappop(queue) # 0, k # 2, 2
        if distance[curn] < curw: # INF < 0 # 2, 2
            continue
        
        for ne, we in to_list[curn]: # 2, 2 # 3, 3 # 3, 4 # 4, 5
            new = curw + we # 0 + 2 = 2 # 0 + 3 = 3 # 2 + 4 = 6 # 2 + 5 = 7
            if new < distance[ne]: # 2 < INF # 3 < INF # 6 < 3 # 7 < INF
                distance[ne] = new # 2 # 3
                heapq.heappush(queue, [new, ne]) # 2, 2 # 3, 3

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

 

주석에는 이해하기 쉽게 할려고 각 들어가는 값들을 순서대로 적어보면서 이해했습니다. 위 같은 풀이방식을 다익스트라 알고리즘이라고 합니다. 모든 정점에서의 최단 거리를 구할려면 플로이드-워셜 알고리즘을 특정 정점에서의 최단 거리를 구할려면 다익스트라를 외워두면 나중에 문제 풀 때 수월할 거 같습니다.

 

다익스트라 알고리즘 참고 블로그 : https://velog.io/@tks7205/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-with-python

다익스트라 알고리즘 with python

 

위 코드에서 heap 을 쓰기 위해서는 import heapq 값을 넣을 때 heappush 값을 뺄 때 heappop 입니다.

 

import heapq 

heap = []
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)

print(heapq.heappop(heap))
print(heapq.heappop(heap))
print(heapq.heappop(heap))

# 1, 4, 7 순서대로 출력

 

heapq 모듈의 heappush() 함수를 이용하여 힙에 원소를 추가하는데 첫번째 인자는 원소를 추가할 대상 리스트이며 두번째 인자는 추가할 원소를 넣어주게 됩니다. 반대로 heappop()을 할 때는 원소를 뺄 대상 리스트를 넣어줍니다.

 

여기까지 정리를 마칩니다 읽어주셔서 감사합니다.