[백준 알고리즘] 9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 (Python)

https://www.acmicpc.net/problem/9694

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

 

소스코드

import sys
import heapq as hq
input = sys.stdin.readline

def dijkstra(start):
  q = []
  min_dis = [float('inf') for _ in range(m)]
  min_dis[start] = 0
  hq.heappush(q,[0,start])

  while q:
    cur_dis,cur_node = hq.heappop(q)

    if min_dis[cur_node] < cur_dis:
      continue

    for next_node, next_dis in graph[cur_node]:
      if min_dis[next_node] > cur_dis + next_dis:
        min_dis[next_node] = cur_dis + next_dis
        pre_node[next_node] = cur_node # 역추적을 위해 이전경로 저장
        hq.heappush(q,[cur_dis + next_dis, next_node])

  return min_dis

t = int(input())
for tc in range(1,t+1):
  n,m = map(int,input().split())
  graph = [[] for _ in range(m)]
  pre_node = [0] * m
  for _ in range(n):
    x,y,z = map(int,input().split())
    graph[x].append([y,z]) # 친구 사이니까 양방향 간선으로 표현
    graph[y].append([x,z])

  t = dijkstra(0)
  if t[m-1] == float('inf'):
    print('Case #{}: {}'.format(tc,-1))
  else: # 경로 역추적 
    path = [m-1] 
    now = m-1
    while now != 0:
      now = pre_node[now]
      path.append(now)
    path.reverse()
    print('Case #{}:'.format(tc),end=' ')
    print(*path)

 

풀이

★ 출발지에서 목적지까지의 최단경로로 이동했을 때, 방문했던 정점을 출력하는 전형적인 문제였습니다. 다익스트라를 수행하면서 방문했던 정점들을 체크하고, 목적지에서부터 다시 출발지점까지 방문했던 정점들을 다시 확인해줍니다 :)