[코딩테스트] 백준 11404번: 플로이드

1. 아이디어

▪ 모든 점에서 모든 점 최단 경로 -> 플로이드

▪ 거리 비용 리스트 INF로 초기화

   - 이때 자기 자신으로 가는 값은 0으로 초기화

▪ 간선 정보 입력 받아서 거리 비용 갱신

▪ for 문 3번 돌리면서 거쳐서 가는 비용이 작을 경우 갱신

  - for 거치는 노드

      - for 시작 노드

         - for 끝 노드

2. 시간복잡도

▪ O(V^3)

3. 변수

▪ 거리 비용 리스트: int[][]

Code

import sys
input = sys.stdin.readline
INF = sys.maxsize

n = int(input())  # 도시의 개수
m = int(input())  # 버스의 개수
rs = [[INF]*(n+1) for _ in range(n+1)]

for i in range(n+1):
    rs[i][i] = 0

for _ in range(m):
    a,b,c = map(int,input().split())
    rs[a][b] = min(rs[a][b], c)

for k in range(1,n+1):
    for j in range(1,n+1):
        for i in range(1,n+1):
            if rs[j][i] > rs[j][k] + rs[k][i]:
                rs[j][i] = rs[j][k] + rs[k][i]

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

11404번: 플로이드