파란색가운의 개발 블로그
이코테 플로이드 워셜 알고리즘 본문
import sys
import heapq
from sys import stdin
from collections import deque
sys.setrecursionlimit(10 ** 8)
sys.stdin.readline
import sys
from sys import stdin
from collections import deque
sys.setrecursionlimit(10 ** 8)
sys.stdin.readline
INF = int(1e9)
N = int(input())
M = int(input())
graph = [[INF] * (N+1) for _ in range(N+1)]
for i in range(1,N+1):
for j in range(1,N+1):
if i == j:
graph[i][j] = 0
for _ in range(M):
a,b,c = map(int,sys.stdin.readline().split())
graph[a][b] = c
for k in range(1,N+1):
for a in range(1,N+1):
for b in range(1,N+1):
graph[a][b] = min(graph[a][b],graph[a][k]+graph[k][b])
for i in range(1,N+1):
for j in range(1,N+1):
if graph[i][j] == INF:
print("INFINITY")
else:
print(graph[i][j],end = " ")
print()
다이나믹 프로그래밍과 매우 유사하다. a->b 와 a->k->b를 비교하여 최솟값 찾기
O(N^3)의 시간이 소요된다
모든 시작점에서 모든 최단루트를 찾는 경우에 사용
'알고리즘 문제 풀이 > 이코테' 카테고리의 다른 글
[이코테] DFS/BFS 실전문제 3 음료수 얼려 먹기 (0) | 2023.11.02 |
---|---|
[이코테 Python] 구현 실전문제 3 게임 개발 (0) | 2023.10.03 |
Chapter 4.구현 / 실전 문제 왕실의 나이트 (0) | 2023.09.29 |
[이코테] 최단경로 문제 3 [전보] 파이썬 풀이 (0) | 2023.07.19 |
[이코테] 최단경로 문제 2 [미래도시] 파이썬 풀이 (0) | 2023.07.19 |