BOJ 11780번: 플로이드 2

www.acmicpc.net/problem/11780

11780번: 플로이드 2

아이디어:

플로이드 문제에 조건을 추가했다. 경로도 같이 출력하라고 한다...

쉽게 봤다가 정말 토할 뻔 했다.. ㅎㅎ..

처음에는 단순히 최솟값을 갱신하면서 k를 저장하면 될 것이라 생각했지만.. k만 저장해서는 안됐다. i-k-j의 경로이더라도 i-k 사이 혹은 k-j 사이에 또 다른 최단 경로가 존재할 수 있기 때문이다. 따라서 이걸 어떻게 하나 참 오래 생각하다가 계속 i-k사이의, k-j사이의 경로를 찾아야 한다는 점에서 재귀적이라고 생각했고, 재귀함수로 경로를 구하면 어떨까 하고 생각했다.

그래서 재귀함수를 통해 i-k사이에 뭔가가 존재하지 않을때까지!! 즉, i-k가 바로 연결되어있고 그게 최단경로일 때까지 재귀함수를 호출하고 k를 저장하고 다음에는 k-j 사이에 뭔가가 존재하지 않을때까지 재귀함수를 호출.. 하는 형태로 짰다. 사실 여기서도 처음에는 그냥 바로 출력했는데 그러면 총 경로의 길이를 계산하는 게 어려워서 따로 배열에 저장하는 형태로 바꿨다.

시간초과가 날까봐 조마조마했는데 넉넉히 통과했다.

정말.. 정말 오래 걸렸다.. 그래도 내 힘으로 풀어서 뿌듯하긴 한데.. 또 봤을 때 다시 풀 수 있을지..ㅎㅎ.. 복습 꼭 해야겠다. 복습할 게 참 많아진다.. 학기 중에 열심히 해야지..

 

#11780번 플로이드 2
import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
INF = 10**9
cost = [[INF]*(n+1) for _ in range(n+1)] #최소 비용
city = [[0]*(n+1)for _ in range(n+1)] #경로

for _ in range(m):
    a, b, c=map(int, sys.stdin.readline().split())
    cost[a][b] = min(cost[a][b], c)

#플로이드 와샬
for k in range(1,n+1): 
    for i in range(1,n+1):
        for j in range(1,n+1):
            if (i==j): continue
            if (cost[i][j]>cost[i][k]+cost[k][j]):
                cost[i][j] = cost[i][k]+cost[k][j]
                city[i][j]=k #중간에 거쳐간 k를 저장

#최소 비용 출력
for i in range(1,n+1):
    for j in range(1,n+1):
        if (cost[i][j]==INF):
            print(0, end=" ")
        else:
            print(cost[i][j], end=" ")
    print()

#경로를 arr에 저장하는 함수   
def path(i, k, j, arr):
    if (k==0): return
    path(i, city[i][k] ,k, arr)
    arr.append(k)
    path(k, city[k][j], j, arr)

#경로 출력
for i in range(1,n+1):
    for j in range(1,n+1):
        if (cost[i][j]==INF):
            print(0)
        else:
            arr = [i] 
            path(i, city[i][j], j, arr)
            print(len(arr)+1, end=" ") #최소 비용에 포함되어 있는 도시의 개수
            for k in arr: #경로 출력
                print(k, end=" ")
            print(j)