[다익스트라] 5251 최소 이동 거리

어떤 도시에 E개의 일방통행 도로가 있고 각 구간이 만나는 연결지점에 0번부터 N번까지의 번호가 붙어있다. 이때 0번 지점에서 N번 지점까지 이동하는데 걸리는 최소한의 거리가 얼마인지 구하라.

---

다익스트라 알고리즘

- 다음 방문하는 노드에 대한 경로를 지금까지 기록한 정보를 통해 최솟값을 갱신한다.

- 기록되어있는 정보에는 출발점부터 해당 번호까지 왔을 때의 최솟값이 저장되어있으며, 계속 갱신될 수 있다.

 

구현

- 2차원 리스트로 그래프를 표현한다.

- 초기에 INF 값으로 초기화한 이유는 이후에 그래프를 탐색하면서 최솟값을 찾을 때 연결되어있지 않은 그래프는 최솟값의 후보에서 벗어나도록 하기위함이다.

- E개의 일방통행 도로를 입력받아 그래프에 저장한다.

    V, E = map(int, input().split())
    INF = 987654321
    graph = [[INF for _ in range(V+1)] for _ in range(V+1)]

    for _ in range(E):
        a, b, w = map(int, input().split())

        graph[a][b] = w

 

- 초기에 메모제이션을 위한 dp리스트에는 INF에 저장되어있다.

- 출발점인 0번 노드는 0으로 설정한다.

- 이후 0번 노드부터 인접한 노드를 탐색하여 다음 경로까지의 최솟값을 dp에 기록한다. 

- for문이 진행되다보면 dp[a] + graph[a][b]는 0번노드 -> a -> b의 거리가된다.

    dp = [INF] * (V+1)
    dp[0] = 0

    for a in range(V+1):
        for b in range(V+1):
            if dp[a] + graph[a][b] < dp[b]:
                dp[b] = dp[a] + graph[a][b]

---

전체 코드

import sys
sys.stdin = open("input.txt")

test_case = int(input())
for tc in range(test_case):
    V, E = map(int, input().split())
    INF = 987654321
    graph = [[INF for _ in range(V+1)] for _ in range(V+1)]

    for _ in range(E):
        a, b, w = map(int, input().split())

        graph[a][b] = w

    dp = [INF] * (V+1)
    dp[0] = 0

    for a in range(V+1):
        for b in range(V+1):
            if dp[a] + graph[a][b] < dp[b]:
                dp[b] = dp[a] + graph[a][b]

    answer = dp[V]
    print("#{} {}".format(tc+1, answer))