[BOJ/PYTHON] 9694. 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 (최단 경로 - 다익스트라)

백준 문제 링크: https://www.acmicpc.net/problem/9694

문제 요약

최고의원을 만나기까지의 친밀도의 합 중에서 가장 작은 값을 구하기

친밀도: (최측근 [1] / 측근 [2] / 비즈니스관계 [3] / 지인 [4])

최고의원을 만날수 있다면 0번 정치인(한신이)를 시작으로 M-1번 정치인(최고의원)까지 만난 순서대로 출력, 최고의원을 만날수 없는 경우엔 -1을 출력

핵심 아이디어

‘관계’가 사람과 사람 간 관계라는 것을 고려했을 때, 사람(정치인)은 정점, 관계는 간선으로 보면 된다. 친밀도의 정도가 정해져있으므로 친밀도를 거리 값으로 간주, 다익스트라 알고리즘으로 풀면 된다.

풀이

# gold3-9694. 무엇을 아느냐가 아니라 누구를 아느냐가 문제다

import sys, heapq
input = sys.stdin.readline

# 최고의원을 만나기까지의 친밀도의 합 중에서 가장 작은 값을 구하기

t = int(input())
for i in range(t): 
    n, m = map(int, input().split()) # 관계의 개수, 정치인의 수
    graph = [[] for _ in range(m+1)]
    for _ in range(n):
        # 정치인, 그의 친구, 두 사람의 친밀도 
        # 친밀도: (최측근 [1] / 측근 [2] / 비즈니스관계 [3] / 지인 [4])
        x, y, z = map(int, input().split())
        graph[x].append((y, z))
        graph[y].append((x, z))
    INF = int(1e9)

    def dijkstra(start):
        q = []
        distance = [INF]*(m+1)
        distance[start] = 0
        heapq.heappush(q, (0, start, [start]))
        while q:
            dist, now, path = heapq.heappop(q)
            if now == m-1: return path
            if distance[now] < dist: continue
            for next_node, next_dist in graph[now]:
                cost = distance[now] + next_dist
                if distance[next_node] > cost:
                    distance[next_node] = cost
                    heapq.heappush(q, (cost, next_node, path + [next_node]))
    
    met_order = dijkstra(0)
    if not met_order: met_order = [-1] 
    print(f'Case #{i + 1}:', *met_order)

if not met_order이면 return값이 비어서 오기에 -1을 출력하기 위해 met_order의 값을 -1로 바꿔준다. 이때, 리스트 안에 담는 이유는 *met_order로 출력하기 위해서이다.

Trouble Shooting

입력값을 단방향 그래프로만 생각해서 틀렸고, 양방향 그래프로 입력 받아줬다.

그리고 print문에서 띄어쓰기 문제로 맞는 답인데 계속 틀렸다고 나왔다..

실행 시간

메모리 33324KB, 시간 128ms (python3)