[11404번] 가장 빠른 버스 노선 구하기(그래프, 최단거리 , 플로이드)

11404번: 플로이드

 

플로이드-워셜

• 시작점 X
• 모든 노드간에 최단 경로 탐색
• 시간복잡도 O(V³) 안좋음 ➡️ 노드의 개수 100~200까지 사용 가능
• 문제 유형
  
  • 시작점이 없고 모든 도시간의 최단거리, 모든 도시 100개 이하
  • 점화식 D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

 

원리

1. 리스트를 선언하고 초기화하기
2. 최단 거리 리스트에 그래프 데이터 저장하기
3. 점화식으로 리스트 업데이트하기

• [Step 1] 1번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다

• [Step 2] 2번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다

• [Step 3] 3번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다

• [Step 4] 4번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다

---

풀이

"""
n개의 도시(2~100)
m 버스의 개수(1~100,000)
모든 도시의 쌍에 관해 가는 데 필요한 비용의 최솟값


a(시작도시) b(도착도시) c(비용 1~100,000)
시작도시와 도착 도시를 연결하는 노선은 1개가 아닐 수 있다

n개의 줄 출력
"""
import sys

# 도시 개수
n = int(input())

# 버스 개수
m = int(input())

# 인접행렬
d = array = [[sys.maxsize for j in range(n+1)] for i in range(n+1)]

# 인접 행렬에 시작 도시와 종료 도시가 같은 자리에 0 저장
for i in range(1, n+1):
    d[i][i] = 0

# 노선 데이터 입력받아 d행렬에 저장
for i in range(m):
    a, b, c = map(int, input().split())
    if d[a][b] > c:
        d[a][b] = c


"""
플로이드 워셜 알고리즘 로직
for 경유지 k에 관해 (1~n)
	for 출발노드 s에 관해 (1~n)
   		for 도착 노드 e에 관해(1~n)
            점화식 d[s][e] = Math.min(d[s][e], d[s][k]+d[k][e])
"""
for k in range(1, n+1):
    for s in range(1, n+1):
        for e in range(1, n+1):
            if d[s][e] > d[s][k] + d[k][e]:
                d[s][e] = d[s][k] + d[k][e]

 
# 출력
for i in range(1, n+1):
    for j in range(1, n + 1):
        if d[i][j] != sys.maxsize:
            print(d[i][j], end=" ")
        else:
            print(0, end=" ")
    print()