[백준] 1719번 택배 ★

💡문제접근

• 최단 거리를 출력하는 것이 아니라 최단 거리를 출력하는 경우 경유해야하는 집하장의 번호를 출력

💡코드(메모리 : 32276KB, 시간 : 1628ms)

import sys
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().strip().split())
graph = [[INF] * (n+1) for _ in range(n+1)]     # 최단거리 정보
result = [[0] * (n+1) for _ in range(n+1)]      # 집하장 정보

for _ in range(m):
    # 집하장간 경로와 두 집하장을 오가는데 필요한 시간(가중치)
    a, b, c = map(int, input().strip().split())
    # 양방향이므로 a → b : c, b → a : c
    graph[a][b] = c
    graph[b][a] = c
    # 거치는 집하장 번호를 저장
    # a → b : b를 경유하므로 b를 저장
    # b → a : a를 경유하므로 a를 저장
    result[a][b] = b
    result[b][a] = a

# 자기 자신에서 자기 자신으로 가는 경우는 0
for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b:
            graph[a][b] = 0

# 직접 이동하는 경우와 다른 집하장을 경유해서 가는 경우를 비교해서 최단경로를 저장
# 만약 다른 집하장을 경유해서 이동한 경우가 최단경로가 된다면 경유한 k를 집하장 번호에 저장
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            if graph[a][b] > graph[a][k] + graph[k][b]:
                graph[a][b] = graph[a][k] + graph[k][b]
                result[a][b] = result[a][k]

# 자기 자신에서 자기 자신으로 가는 경우는 -을 출력
for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b:
            result[a][b] = "-"
            print(result[a][b], end = " ")
        else:
            print(result[a][b], end = " ")
    print()

💡소요시간 : 47m