(Python/🥇2)백준알고리즘 11780번: 플로이드2

문제 바로가기 

 

문제:

n(1 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

출력:

먼저, n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다. 그 다음에는 n×n개의 줄을 출력해야 한다. i×n+j번째 줄에는 도시 i에서 도시 j로 가는 최소 비용에 포함되어 있는 도시의 개수 k를 출력한다. 그 다음, 도시 i에서 도시 j로 가는 경로를 공백으로 구분해 출력한다. 이때, 도시 i와 도시 j도 출력해야 한다. 만약, i에서 j로 갈 수 없는 경우에는 0을 출력한다.

 

 

풀이:

 

graph = 플로이드를 저장하기 위함이고 paht는 최단거리 길을 저장하기 위함이다

 

 

 

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

city = int(input())
bus = int(input())

graph = [[1e9]*(city+1) for _ in range(city+1)]
path = [[-1]*(city+1) for _ in range(city+1)]
for i in range(bus):
    a, b, e = map(int,sys.stdin.readline().rstrip().split(" "))
    graph[a][b] = min(graph[a][b],e)
    path[a][b] = a # 길 저장 a 에서 b 가는 길에 a

for i in range(1,city+1):
    for j in range(1,city+1):
        if i == j:
            graph[i][j] = 0
# 플로이드-와샬, 최단거리 일때 path저장             
for k in range(1, city + 1): # 경유지
    for a in range(1, city + 1): # 출발지
        for b in range(1, city + 1): # 도착지
            d = graph[a][k] + graph[k][b]
            if graph[a][b] > d:
                graph[a][b] = d
                path[a][b] = path[k][b]
# 최소비용 출력
for i in range(1,city+1):
    for j in range(1,city+1):
        print(graph[i][j] if not graph[i][j] == 1e9 else 0, end=" ")
    print()
    
for i in range(1, city + 1):
    for j in range(1, city + 1):
        if graph[i][j] == 1e9 or graph[i][j] ==0:
            print(0)
        else:
            end = j
            lst = []
            while True:
                if end == i:
                    lst.append(i)
                    break
                lst.append(end)
                end = path[i][end]
            print(len(lst), end=" ")
            print(*lst[::-1])

예를 들어, 도시 A에서 도시 B로 가는 최소 비용 경로가 A -> C -> D -> B 일때. 그리고 경유지 k가 C일 때, graph[A][B]에 저장된 최소 비용은 A -> B 경로의 비용이다.. 이때, 경유지 C를 거치는 비용이 더 작아진다면, graph[A][B]를 더 작은 비용으로 업데이트하고, path[A][B]를 path[C][B]로 업데이트하여 A에서 B로 가는 최소 비용 경로를 A -> C -> B로 갱신한다.

나중에 역추적을 하기 위함이다.

 

마지막 포문에서 

 

for i in range(1, city + 1):
    for j in range(1, city + 1):
        if graph[i][j] == 1e9 or graph[i][j] ==0:
            print(0)
        else:
            end = j
            lst = []
            while True:
                if end == i:
                    lst.append(i)
                    break
                lst.append(end)
                end = path[i][end]
            print(len(lst), end=" ")
            print(*lst[::-1])

 

역추적을 하는것이다.

 

예를들어 도시  1> 5 를 1>2>4>5 라고 가정을 하겠다.

그럼 i = 1 j = 5 가 나오고 end는 5이다 

while 문을 돌리면서 역추적 하면 서 추가해주는것이다.

lst 에 5가 들어가고 그다음 4를 가르켜야하므로 path[1][5] 를 하면 path[k][5] 이 k 가 4가 나오게된다.

그거를 자기 자신이 될때까지 하면 된다.

 

 

https://windy7271.tistory.com/entry/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

플로이드-워셜 알고리즘