[BOJ] 9694. 무엇을 아느냐가 아니라 누구를 아느냐가 문제다

www.acmicpc.net/problem/9694

9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다

 

문제: 최고 의원을 만나는 루트를 출력하라.

 

문제 이해하기!!

최측근 [1] / 측근 [2] / 비즈니스관계 [3] / 지인 [4]

이라는 관계가 있는데, 이 관계를 코스트라고 생각하고 다익스트라로 풀면 되는 문제였습니다.

 

제가 푼 방식을 설명하자면,

1. 출력할 루트를 저장할 배열을 하나 만든다 - 여기서는 dp

2. 입력받은 "사람 - 사람 - 친밀관계"를 그래프형식으로 저장한다. - 여기서는 딕셔너리 사용

3. 해당 그래프를 0부터 시작해서 최소비용을 가지는 사람관계부터 탐색한다.

4. 비용은 탐색하면서 중첩으로 더하여 최소 값을 찾으므로, 최고의원이랑 컨택할 때는 무조건 최소 값이다. 그러므로 break한다.

 

끝

 

코드:

import heapq
from collections import defaultdict
from sys import stdin
# stdin = open('input.txt', 'r')
input = stdin.readline

T = int(input())
for _ in range(T):
    res = []
    N, M = map(int, input().split())
    dp = [[] for i in range(M)]
    dic = defaultdict(list)
    for i in range(N):
        s, e, c = map(int, input().split())
        dic[s].append((c, e))
        dic[e].append((c, s))
    Q = [(0, 0, 0)]
    visit = [False] * M
    while Q:
        c, e, s = heapq.heappop(Q)
        if visit[e]:
            continue
        else:
            dp[e] = dp[s] + [e]
        if e == M-1:
            break
        visit[e] = True
        for nc, ne in dic[e]:
            heapq.heappush(Q, (nc + c, ne, e))

    print(f"Case #{_+1}:", end=" ")
    if dp[M-1]:
        print(*dp[M-1])
    else:
        print(-1)