[BOJ 11780 파이썬] 플로이드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을 출력한다.

예제 입력 1 

5
14
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
3 5 10
3 1 8
1 4 2
5 1 7
3 4 2
5 2 4

예제 출력 1 

0 2 3 1 4
12 0 15 2 5
8 5 0 1 1
10 7 13 0 3
7 4 10 6 0
0
2 1 2
2 1 3
2 1 4
3 1 3 5
4 2 4 5 1
0
5 2 4 5 1 3
2 2 4
3 2 4 5
2 3 1
3 3 5 2
0
2 3 4
2 3 5
3 4 5 1
3 4 5 2
4 4 5 1 3
0
2 4 5
2 5 1
2 5 2
3 5 1 3
3 5 2 4
0

 

 

해당 문제를 포스팅하기로 한 이유는 (최단경로이든 아니든)그래프를 탐색하고 원하는 경로를 출력해야하는 문제가 많음을 느꼈고, 내가 푸는 방식이 약간은 다른 사람들의 풀이와는 조금 다른 점이 있는 것 같아 포스팅하고자 했다.

 

풀이

---

일단 기본적인 플로이드 와샬에 대한 설명은 생략하겠다. (간단히 설명하면, 3중 포문을 이용하여 갈 수 있는 모든 경로를 탐색하는 것이다. 가령 5개의 node가 있다고 하고 1->5의 경로를 구할 때, 1->2->5, 1->3->5 ... 모두 탐색하며 최단 경로를 찾는 알고리즘이다.)

 

플로이드 와샬을 돌려주는데, 이때 나는 그래프 2차원 배열에(graphp[i][j]이면 i부터 j까지 가는데 드는 비용) 지금까지 탐색하는데 든 비용만 넣는 것이 아니라 3차원 배열로 선언해 graphp[i][j] 에 [지금까지 탐색하는데 든 비용,지금까지 탐색한 경로] 이렇게 저장해주었다. 경로는 list로 저장해주어도 되고 단순 String으로 저장해도 무방하다. (배열을 넣을 땐 더 짧은 경로를 넣어주기 위해서 copy하고 append 하는 등의 시간이 추가되므로 String을 선호한다.)

 

if graph[j][k][0] > graph[j][i][0] + graph[i][k][0]:
	graph[j][k][0] = graph[j][i][0] + graph[i][k][0]        
	graph[j][k][1] = graph[j][i][1] +" "+" ".join(graph[i][k][1].split()[1:])

 

플로이드 와샬을 할 때, 다음과 같이 현재 경로까지 든 비용보다 어떤 경로를 거쳐서 올 때 드는 비용이 더 적다면 더 적은 비용으로 업데이트 해주어야 되는데, 경로도 함께 업데이트 해야한다.

 

이때, i를 거친 j부터 k까지의 최단 경로를 탐색하고 있다면, 비용과 마찬가지로 j부터 i까지의 경로와  i부터 j까지의 경로를 더해주어야하는데 이때, i 경로가 겹치기 때문에 이를 빼고 더해주어야한다. 위 코드는 해당 부분을 고려해준 것이다.

 

이 문제에서는 꼭!! 갈 수 없는 노드를 0으로 표시해주는 것을 잊지 말아야한다.

 

코드

---

import sys

n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())

INF = sys.maxsize

graph = [[[INF,str(i+1)] for i in range(n)] for _ in range(n)]

for i in range(n):
    graph[i][i][0] = 0

for _ in range(m):
    a,b,c = map(int,sys.stdin.readline().rstrip().split())
    if graph[a-1][b-1][0] > c:
        graph[a-1][b-1][0] = c
        graph[a-1][b-1][1] = str(a) +" "+str(b)
    
for i in range(n):##거치는 점
    for j in range(n):##시작 점
        for k in range(n):## 끝점
            if graph[j][k][0] > graph[j][i][0] + graph[i][k][0]:
                graph[j][k][0] = graph[j][i][0] + graph[i][k][0] ##비용
                graph[j][k][1] = graph[j][i][1] +" "+" ".join(graph[i][k][1].split()[1:]) ##경로


for i in range(n):
    temp = ""
    for j in range(n):
        if graph[i][j][0] == INF:
            temp += "0 "
        else:
            temp += str(graph[i][j][0]) + " "
    print(temp) 

for i in range(n):
    for j in range(n):
        temp = ""
        if i == j:
            print(0)
        elif len(graph[i][j][1].split()) < 2:
            print(0)
        else:
            temp += str(len(graph[i][j][1].split())) + " "
            temp += graph[i][j][1]
            print(temp)

 

누구나 편한 방법은 있겠지만, 나는 그래프 탐색의 경우엔 해당 노드를 기준으로 배열에 경로를 같이 나타내주는 것이 훨씬 편하고 활용하기 좋았다😀

 

 

이외에도 그래프 경로를 출력해야하는 문제들은 다음과 같다.

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

13913번: 숨바꼭질 4

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

11779번: 최소비용 구하기 2