1753

날짜 : 2022. 12. 08

사용 언어 : python

 

문제

 

 

코드

import sys
import heapq

INF = int(1e9)
v, e = map(int, sys.stdin.readline().split())  # 정점의 개수, 간선의 개수
k = int(sys.stdin.readline())  # 시작정점
graph = [[] for i in range(v + 1)]  # 그래프
distance = [INF] * (v + 1)  # 시작점 기준 각 노드간 최소거리

for _ in range(e):
    a, b, c = map(int, sys.stdin.readline().split())  # 시작, 도착, 길이
    graph[a].append((b, c))

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))  # start 로 가기위한 최단거리 0
    distance[start] = 0

    while q:
        d, now = heapq.heappop(q)  # now 까지의 최단거리 추출
        if distance[now] < d : continue
        for i in graph[now]:
            cost = d + i[1]  # now - 인접노드간 거리
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))


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

 

 

풀이

- 다익스트라 알고리즘을 활용한 문제였다.

 

 

알게된 점

- 아직은 바로바로 알고리즘이 나오는 단계는 아닌듯 하다.

- 계속 문제를 풀어보면서 DFS, BFS처럼 생각하면 바로 꺼낼 수 있도록 연습이 필요해 보인다.

 

 

참고 사이트

-