백준 11780번: 플로이드 2 [python]

난이도 : 골드 2
유형 : 플로이드-워셜, 역추적
https://www.acmicpc.net/problem/11780

역추적을 제외하면 풀어본 문제이다.
백준 11404번: 플로이드 [python]

모든 정점에서 모든 정점으로의 최소거리를 구할 때 쓰는 알고리즘이 플로이드-워셜 알고리즘이었는데 3중 for문을 돌려서 distance[i][j] ( i -> j 최단거리) 형식으로 모든 정점에서 모든 정점으로의 최단거리를 저장한다.

3중 for 문이기에 O(N^3) 으로 시간복잡도가 크기에 N이 100 이하일때 효과적인 알고리즘이었다.

주요 로직

# 플로이드 워셜 수행
for k in range(1, n+1): # 경유지
    for i in range(1, n+1): # 출발지
        for j in range(1, n+1): # 도착지
            distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
            # i -> j 보다 i -> k -> j 로 우회하여 가는게 더 작다면, 그걸로 갱신

해답 및 풀이

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())

INF = int(1e9)

# dist = 최단거리 테이블 
dist = [[INF] * (n+1) for _ in range(n+1)]

# 경로 복원을 위한 next 배열
# next[i][j] =  도시 i에서 도시 j로 가는 최단 경로를 따라갈 때, i에서 출발한 직후에 바로 가야 하는 다음 도시
# i -> a -> b -> c -> j 라면 a를 저장한다는 뜻
just_next_node = [[0] * (n+1) for _ in range(n+1)]

# 자기 자신으로 가는 비용은 0
for i in range(1, n+1):
    dist[i][i] = 0

# 간선 정보 입력
for _ in range(m):
    a, b, c = map(int,input().split())
    # a->b로 가는 비용이 여러 개 있을 수 있으므로 최솟값만 저장
    if c < dist[a][b]:
        dist[a][b] = c 
        just_next_node[a][b] = b  # 경로가 a -> b 라면 a 바로 다음 노드는 당연히 b

# 플로이드 워셜
for k in range(1, n+1):  # 경유지
    for i in range(1, n+1): # 출발지
        for j in range(1, n+1): # 도착지
            if dist[i][k] + dist[k][j] < dist[i][j]: # k를 경유해서 가는 것이 다이렉트로 i->j로 가는 것보다 비용이 작다면
                dist[i][j] = dist[i][k] + dist[k][j]
                just_next_node[i][j] = just_next_node[i][k] # i -> j 로 바로 가는 것보다 i -> k -> j 로 가는게 더 빠르기 때문에 i -> j 일떄 i다음 노드는 결국, i -> k -> j 의 바로 다음 노드와 같음을 알 수 있다.

# 이쯤에서 just_next_node 왜 저장하는 지
# 나중에 경로를 복원할 수 있다.
# i에서 j로 갈 때 next_node[i][j]를 본다 → 첫 번째 도시를 알 수 있음
# 그 도시에서 다시 j로 갈 때 next_node[that][j]를 본다 → 두 번째 도시를 알 수 있음
# 이런 식으로 쭉 따라가면 전체 경로를 알 수 있음


# 최단거리 dist 배열 출력
for i in range(1,n+1):
    for j in range(1,n+1):
        if dist[i][j] == INF:
            print(0, end=' ')
        else:
            print(dist[i][j], end=' ')
    print()

# 경로 출력
for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j or dist[i][j] == INF:
            # 갈 수 없거나, 자기 자신으로 가는 경우
            print(0)
        else:
            # 경로 복원
            path =[i]
            cur = i
            while cur != j:
                cur = just_next_node[cur][j]
                path.append(cur)
            #경로 길이와 경로 출력
            print(len(path), *path)