[백준] 11404번-(Python 파이썬) - Floyd-Warshall
1313 단어 백준floyd-warshallfloyd-warshall
문제링크 : https://www.acmicpc.net/problem/11404
이번 문제는 플로이드-워셜 알고리즘 문제이다.
플로이드 워셜은 모든 정점 사이의 최단 경로를 찾는 탐색 알고리즘이다.
- 하나의 정점에서 다른 정점으로 갈 수 있는 최소비용을 배열에 값을 저장한다. (갈 수 없으면 inf로 배열값 저장)
- 3중 for문을 통해 거쳐가는 정점을 설정한 후 해당 정점을 거쳐가서 비용이 줄어드는 경우 값을 바꿔준다.
- 위의 과정을 반복해 모든 정점 사이의 최단 경로를 탐색한다.
DP라고도 볼 수도 있으며 코드는 간단하여 설명은 코드에 주석으로 하였다.
import sys
input = sys.stdin.readline
inf = sys.maxsize
n = int(input())
m = int(input())
#최단 경로를 담는 배열
dist = [[inf] * n for _ in range(n)]
for _ in range(m):
a, b, c = map(int, input().split())
if dist[a-1][b-1] > c:
dist[a-1][b-1] = c
for k in range(n): #거치는 점
for i in range(n): #시작 점
for j in range(n): #끝 점
# k를 거쳤을 때 더 적은 경로
if i != j and dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]
for i in dist:
for j in i:
if j == inf:
print(0, end=" ")
else:
print(j, end=" ")
print()
Author And Source
이 문제에 관하여([백준] 11404번-(Python 파이썬) - Floyd-Warshall), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hamfan524/백준-11404번-Python-파이썬-Floyd-Warshall저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)