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

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

1753번: 최단경로

처음 다익스트라 문제를 풀었을 때는, 코드를 짜는데 시간이 되게 오래 걸렸었습니다.

근데, 골드 4 난이도임에도 빠른 시간 내에 코드를 짜서 살짝 울컥했습니다.

공부해왔던게 효과가 있구나 라는 생각과 동시에 저도 모르게 살짝 울컥하더라구요.. 너무 뿌듯했습니다.

이런 기분때문에 공부를 계속할 수 있는 것 같습니다.

코딩 공부하는 모든 분들도 성취감을 느껴가며 즐겁게 공부하셨으면 좋겠습니다!

 

문제: 방향그래프가 주어졌을 때, 모든 정점으로의 최단거리를 구하는 문제입니다.

 

풀이 방법: 다익스트라 알고리즘을 활용하였습니다.

 

풀이 코드:

import sys
import heapq

INF =1e9

v,e = map(int,sys.stdin.readline().split())

k = int(input())

graph = [[]for _ in range(v+1)]

dist = [INF] * (v+1)
dist[k] = 0

for _ in range(e):
    start, end, cost= map(int,sys.stdin.readline().split())
    graph[start].append((cost,end))

def dijkstra(k):
    queue = []
    heapq.heappush(queue,(0,k))

    while queue:
        cost,node = heapq.heappop(queue)

        for nextCost,nextNode in graph[node]:
            distance = dist[node] + nextCost
            if distance < dist[nextNode]:
                dist[nextNode] = distance
                heapq.heappush(queue,(distance,nextNode))

dijkstra(k)

for i in range(1,v+1):
    if dist[i] == INF:
        print('INF')
    else:
        print(dist[i])

풀이 설명:

핵심은 다익스트라 알고리즘 이므로, 다익스트라 알고리즘을 보고 가겠습니다.

def dijkstra(k):
    queue = []
    heapq.heappush(queue,(0,k))

초기 값은 다익스트라 함수에 주어진 시작 노드 입니다.

이때 cost는 0으로 설정하여 heapq에 넣어줬습니다.

 

while queue:
    cost,node = heapq.heappop(queue)

    for nextCost,nextNode in graph[node]:
        distance = dist[node] + nextCost
        if distance < dist[nextNode]:
            dist[nextNode] = distance
            heapq.heappush(queue,(distance,nextNode))

이후 비용을 계산하는 반복문 입니다.

 

heapq에서 순차적으로 값을 꺼내옵니다.

 

cost와 node가 꺼내지는데요.  다음과 같이 heapq에서 꺼내진 node로 부터 연결된 노드들을 탐색합니다.

 

for nextCost,nextNode in graph[node]:
    distance = dist[node] + nextCost
    if distance < dist[nextNode]:
        dist[nextNode] = distance
        heapq.heappush(queue,(distance,nextNode))

node - newNode까지의 거리를 계산하고, 거리를 저장하는 배열인 dist에 저장된 값과 비교해줍니다.

현재 계산된 거리의 Cost가 더 낮을 경우, dist배열에 갱신해주고 갱신된 Cost와 함께 heapq에 넣어주는 과정을 반복시킵니다.

 

이를 통해, 시작 노드로 부터 연결된 모든 노드들을 탐색하게 됩니다.

 

 

다익스트라처럼 다른 알고리즘들도 잘 활용할 수 있도록 공부하자는 마음을 다잡는 문제였습니다.