[SWEA][D4][#05251] 최소 이동 거리

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

A도시에는 E개의 일방통행 도로 구간이 있으며, 각 구간이 만나는 연결지점에는 0부터 N번까지의 번호가 붙어있다.

구간의 시작과 끝의 연결 지점 번호, 구간의 길이가 주어질 때, 0번 지점에서 N번 지점까지 이동하는데 걸리는 최소한의 거리가 얼마인지 출력하는 프로그램을 만드시오.

모든 연결 지점을 거쳐가야 하는 것은 아니다.

그림 생략

그림은 입력인 N=2, E=3, 시작과 끝 지점, 구간 거리가 아래와 같은 경우의 예이다.

0 1 1 0 2 6 1 2 1

입력

첫 줄에 테스트 케이스의 개수 T가 주어지고, 테스트 케이스 별로 첫 줄에 마지막 연결지점 번호N과 도로의 개수 E가 주어진다.

다음 줄부터 E개의 줄에 걸쳐 구간 시작 s, 구간의 끝 지점 e, 구간 거리 w가 차례로 주어진다. ( 1<=T<=50, 1<=N, s, e<=1000, 1<=w<=10, 1<=E<=1000000 )

출력

각 줄마다 “#T” (T는 테스트 케이스 번호)를 출력한 뒤, 테스트 케이스에 대한 답을 출력한다.

예제

입력

3
2 3
0 1 1
0 2 6
1 2 1
4 7
0 1 9
0 2 3
0 3 7
1 4 2
2 3 8
2 4 1
3 4 8
4 6
0 1 10
0 2 7
1 4 2
2 3 10
2 4 3
3 4 10

출력

#1 2
#2 4
#3 10

My Sol

from collections import deque

T = int(input())
for tc in range(1, T+1):
    V, E = map(int, input().split())
    G = [[] for _ in range(V+1)]
    for _ in range(E):
        u, v, w = map(int, input().split())
        G[u].append((v, w))

    D = [0xffffff]*(V+1)
    D[0] = 0

    Q = deque()
    Q.append(0)

    while Q:
        u = Q.popleft()
        for v, w in G[u]:
            if D[v] > D[u] + w:
                D[v] = D[u] + w
                Q.append(v)
    print(f'#{tc} {D[V]}')

간선완화를 사용하여 문제를 해결할 수 있었다. Q에서 꺼낸 u가 기준점, 기준점의 인접 노드 G의 각각의 v, w에 대하여 시작점부터 u까지의 최단경로인 D[u]와 u~v의 가중치인 w를 더한 값이 D[v]보다 작은 경우 u를 거치는 것이 최단경로이므로 갱신해주고, v를 Q에 넣어준다.

결과

PASS

모범답안

T = int(input())
for tc in range(1, T + 1):
    # N : 정점의 수
    # E : 간선의 수
    N, E = map(int, input().split())
 
    # 정점의 수 최대값 * 가중치 최대값 = 10000
 
    memo = [10000] * (N + 1)
 
    # 시작점은 0으로 초기화
    memo[0] = 0
 
    for i in range(E):
        s, e, w = map(int, input().split())
        memo[e] = min(memo[e], memo[s] + w)
 
    print(f'#{tc} {memo[N]}')

동기의 코드인데 memoization과 dp를 활용하는 방식으로 간단하게 문제를 해결하셨다.