백준 1140(플로이드) -Python(파이썬) - 플로이드워셜 알고리즘

11404번: 플로이드

예제 풀이

시작 도시와 도착 도시를 연결하는 노선이 하나가 아닐 수 있으므로 또 입력 받을 경우 최단 거리로 입력 받게 만든다.

그렇게 입력 받은 노드들을 출발 노드를 세로, 도착 노드를 가로로 표를 작성한다.

1 ) 1번 노드를 거처셔 표 작성

2) 2번 노드를 거쳐서 표 작성

3) 3번 노드를 거쳐서 표 작성

 

이런식으로 노드마다 경로노드라고 할 경우 표를 갱신해서 표현한다. 

그렇게 되면 결국 밑의 표와 같이 표가 나오게 된다.

출발 \ 도착	1	2	3	4	5
1	0	2	3	1	4
2	12	0	15	2	5
3	8	5	0	1	1
4	10	7	13	0	3
5	7	4	10	6	0

 

---

문제 풀이

① 표로 입력 받을 때, 원래 있던 값과 비교해서 최솟값 입력 받기
② 시작점과 도착점이 같은 경우 0으로 입력
③ 경로노드를 for문으로 1부터 5까지 표 입력하기

💻Python(파이썬)

import sys
INF = int(1e9)
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
graph = [[INF]*(n+1) for _ in range(n+1)]
for i in range(m):
    a,b,c = map(int,sys.stdin.readline().split())
    #시작도시와 도착 도시를 연결하는 노선이 하나가 아닐 수도 있으므로 최솟값 입력받기
    graph[a][b]=min(graph[a][b],c)

#시작점,도착점이 같은 경우 0으로 입력
for i,arr in enumerate(graph):
    arr[i]=0

#경로 노드
for p in range(1,n+1):
    #시작노드
    for q in range(1,n+1):
        #도착노드
        for r in range(1,n+1):
            graph[q][r]=min(graph[q][r],graph[q][p]+graph[p][r])

for i in range(1,n+1):
    for j in range(1,n+1):
        if graph[i][j]!=INF:
            print(graph[i][j],end=" ")
        else:
            print(0,end=" ")
    print()