https://www.acmicpc.net/problem/11404
11404번: 플로이드
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가
www.acmicpc.net
문제 회고
드디어 모든 노드 쌍의 최단거리를 구하는 알고리즘인 플로이드 워셜 알고리즘
플로이드 워셜 알고리즘의 아이디어는 '거쳐가는 정점'을 기준으로 최단거리 갱신 => 먼저 코드를 보고 이해해보기
시간 복잡도: 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
오히려 앞선 다익스트라 알고리즘보다 코드 이해하기는 쉬웠지만 추가로 개념을 더 정리해야겠다!!
'알고리즘 > 백준' 카테고리의 다른 글
[백준]1956 운동(Python) (2) | 2024.01.17 |
---|---|
[백준]11657 타임머신(Python) (1) | 2024.01.15 |
[백준]1753 최단경로(Python) (1) | 2024.01.13 |
[백준]9251 LCS(Python) (0) | 2024.01.11 |
[백준]1890 점프(Python) (0) | 2024.01.11 |