[백준]11404 플로이드(Python)

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

11404번: 플로이드

 

문제 회고

 

드디어 모든 노드 쌍의 최단거리를 구하는 알고리즘인 플로이드 워셜 알고리즘 

플로이드 워셜 알고리즘의 아이디어는 '거쳐가는 정점'을 기준으로 최단거리 갱신 => 먼저 코드를 보고 이해해보기 

 

시간 복잡도: O(N^3)

 

코드

import sys

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

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

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

def floyd():
    for cross in range(1, n+1):  # 거쳐가는(cross) 노드가 기준(가장 바깥쪽 반복문)
        for s in range(1, n+1): # 거쳐가는 노드를 기준으로 모든 출발 노드와 도착 노드의 조합 확인
            if cross == s:
                continue
            for e in range(1, n+1):
                if cross == e or s == e:    # 거쳐가는 노드 == 도착 노드 or 출발 노드 == 도착 노드는 x
                    continue

                if graph[s][e] > graph[s][cross] + graph[cross][e]: # 더 적은 비용으로 갱신
                    graph[s][e] = graph[s][cross] + graph[cross][e]

graph = [[INF] * (n+1) for _ in range(n+1)]

for i in range(1, n+1):
    graph[i][i] = 0     # 자기 자신에서 자기 자신으로 가는 비용 초기화

# 간선 정보 입력 받기
for _ in range(m):
    s, e, w = map(int, input(). split())    # s에서 e로 가는 비용 w
    if graph[s][e] > w: # 만약 이미 등록된 노선 중 더 적은 비용의 노선이 있다면 갱신
        graph[s][e] = w

floyd()

for s in range(1, n + 1):
    for e in range(1, n + 1):
        # 도달할 수 없는 경우 0을 출력
        if graph[s][e] == INF:
            print(0, end = " ")
        # 도달할 수 있는 경우 거리를 출력
        else:
            print(graph[s][e], end = " ")

    print()

 

문제 회고

 

24/01/14

오히려 앞선 다익스트라 알고리즘보다 코드 이해하기는 쉬웠지만 추가로 개념을 더 정리해야겠다!!