백준 11405 (python): 경로 찾기

import sys
input = sys.stdin.readline

INF = int(1e9) # 무한을 의미하는 10억 값 설정
n = int(input())

graph = []

for _ in range(n):
    path = list(map(int, input().split()))
    
    for j in range(len(path)): # 0 이라면 INF로 변경하여 넣어주기
        if path[j] == 0:
            path[j] = INF
    
    graph.append(path)
            
for k in range(n):
    for a in range(n):
        for b in range(n):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
            

for a in graph:
    for b in a:
        if b != INF:
            print(1, end=" ")
        else:
            print(0, end=" ")
    print()

 

플로이드 워셜 알고리즘의 시간 복잡도는 O(N^3)...

파이썬은 초당 2000만번이 가능

따라서 노드의 개수가 300 이하일 때 사용 가능하다.

 

(다익스트라는 N^2이므로 5000개 이하일 때 사용 가능함)