[BOJ][🟡4][백준#09694] 무엇을 아느냐가 아니라 누구를 아느냐가 문제다

문제 출처

BAEKJOON Online Judge #9694

문제

한신이는 젊고, 똑똑하고 매우 유명한 정치인이다. 그럼에도 그는 여전히 자신의 성공을 위해서도 인간관계는 중요한것이라고 믿고있다. 다음달에 열릴 국회의원선거에서 한신이는 자신의 당이 반드시 이기길 희망한다. 그러기 위해서 최고의원의 지지가 필요하다.

이 최고의원의 지지를 받기위해 한신이는 전략을 세웠다. 그는 그 최고의원을 직접적으로 만날수 없다면 그를 알고있는 인맥을 이용하여 만날것이다. 이것을 위해서 우선 정치인들의 친밀도를 조사하였는데 친밀도를 다음 4단계로 나누어서 기록해놓았다. 최측근 [1] / 측근 [2] / 비즈니스관계 [3] / 지인 [4] [두 사람의 관계는 이 4가지 경우중 반드시 해당되며, 적(enemy)는 존재하지 않는다.] 한신이는 지인보다는 최측근 친구에게 소개받기 원한다. 그래서 최고의원을 만나기까지의 인맥간 친밀도의 합을 최소화하고 싶어한다. N명의 정치인 명단으로부터 그들의 인맥 친밀도가 주어진다. 정치인 리스트를 보고 한신이가 최고의원을 만나기까지의 친밀도의 합 중에서 가장 작은 값을 구하면 된다.

입력

맨위 첫 번째 줄에 T(1 <T< 100)는 테스트케이스 수를 의미한다. 이것을 따라 다음줄에 각 테스트 케이스가 주어지는데, 첫 번째 줄에는 N과 M이 주어진다. N(N ≤ 20)은 관계의 개수를 의미하며, M(5 ≤M≤ 20)은 정치인의 수를 나타낸다. 이 다음 N줄에는 정치인 x, 그의 친구 y (0 ≤x,y< M), 두사람간의 친밀도 z(1 ≤z≤ 4)를 입력받는다. 정치인 0번은 한신이를 나타내고 M-1은 최고의원을 의미한다.

출력

각 테스트 케이스는 “Case #x: “의 형식으로 출력되며 x는 케이스 번호(1부터 시작)을 의미한다. 콜론뒤에 한신이가 최고의원을 만날수 있다면 0번 정치인(한신이)를 시작으로 M-1번 정치인(최고의원)까지 만난 순서대로 출력하면 되고, 최고의원을 만날수 없는 경우엔 -1을 출력하면 된다.

예제

입력

2
7 5
0 1 2
1 3 4
0 2 1
0 4 3
3 2 3
3 4 4
2 4 1
3 5
0 1 2
1 3 4
4 2 1

출력

Case #1: 0 2 4
Case #2: -1

My Sol

import sys
input = sys.stdin.readline
from collections import deque

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

    check = [[1e5, []] for _ in range(M+1)]
    check[0] = [0, [0]]
    Q = deque()
    Q.append((0, 0))
    while Q:
        u, cost = Q.popleft()
        for v, w in G[u]:
            if not (cost + w < check[v][0]): continue
            check[v] = [cost + w, check[u][1]+[v]]
            Q.append((v, cost+w))

    ret = [-1] if check[M-1][0] == 1e5 else check[M-1][1]
    print(f'Case #{t+1}:', *ret)

다익스트라 알고리즘을 활용하며 문제를 풀었다. 단지 최소비용이 아니라 경로를 구해야했고, 다익스트라 알고리즘은 최소비용을 비교하여 갱신하는 구조이기 때문에 최소비용을 갱신할 수 있다면 경로까지 갱신할 수 있도록 기본 배열에 비용과 경로를 넣어 초기화해주었다.

접근 방식

1. 비용 체크 배열 check를 [1e5, []]로 초기화한다.
2. 시작 지점을 [0, [0]]으로 초기화한다.
3. 이를 deque Q에 넣는다. 앞으로 최소경로로 갱신되는 지점은 deque에 넣을 것이다.
4. 매 반복의 시작점 u와 연결된 G[u]의 지점들을 v, u와 v 사이의 비용을 w로 둔다.
5. 만약 cost, 즉 0번부터 u까지의 최소비용과 w를 더한 값이 현재 0번부터 v까지의 최소비용보다 적은 경우, 최소비용과 경로를 갱신해준다.
6. 갱신했으므로 Q에 최소비용과 경로를 추가해준다. 이것이 또다른 시작점이 될 것이다.
7. 가능한 모든 갱신을 마친 뒤, M-1지점의 최소비용을 체크한다.
8. 이것이 1e5라면 갱신이 안 된 것이므로 -1이고, 아니라면 갱신을 한 것이므로 path를 출력해준다.

결과

맞았습니다!!