[백준 2024/02/26] 1753번 최단경로

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

1753번: 최단경로

 

1. 접근 방법

전형적인 dijkstra 문제였다. 

코드에 주석을 달아서 더 설명해 보도록 하겠다.

 

2. 코드

import heapq

INF = int(1e9)


def findCheapestPrice(n, src, nodes): # edge들을 저장한 nodes를 넘겨 받았다.
    dist = [INF] * (n + 1) # dist라는 list에 각각의 노드에 들어가는 최솟값을 INF로 저장하였다.
    graph = [[] for _ in range(n + 1)]# nodes를 dijkstra 입맛에 맞게 편집하기 위해 graph 선언.
    q = []

    for a, b, c in nodes:
        graph[a].append((b, c)) # a : 시작 노드, b: 도착 노드, c: weight

    heapq.heappush(q, (0, src)) # 시작 노드인 src에 대해서 weight 를 0 으로 두어 가장 먼저 pop이 되도록 하였다.

    dist[src] = 0 #시작 노드이므로, 값을 0으로 저장.

    while q:
        acc, cur = heapq.heappop(q) # 최소 acc를 가지는 것을 pop

        if dist[cur] < acc: # 여태까지 저장한 값보다 현재 dist[cur] 에 저장된 값이 적다면 continue
            continue

        for adj, d in graph[cur]: # 해당 노드로부터 인접 노드들을 하나씩 꺼내온다.
            cost = acc + d # 저장된 것 + 새로 이동하면서 얻게 될 값
            if cost < dist[adj]: # cost가 더 작다면, 새로운 값으로 대치해준다.
                dist[adj] = cost
                heapq.heappush(q, (cost, adj)) #heapque에다가 바꾼 값을 다시 넣어준다. 현재까지의 경로를 넣어주는 느낌

    return dist


def input_nodes(n, e):
    nodes = []
    for _ in range(e):
        nodes.append(list(map(int, input().split())))
    return nodes


def print_nodes(dist, n):
    for i in range(1, n + 1):
        if dist[i] == INF:
            print("INF")
        else:
            print(dist[i])


def main():
    n, e = map(int, input().split())
    start = int(input())
    dist = findCheapestPrice(n, start, input_nodes(n, e))
    print_nodes(dist, n)


if __name__ == "__main__":
    main()