문제 출처
https://www.acmicpc.net/problem/11404
문제 풀이
문제 자체는 전형적인 최단 경로 문제이다.
다만 문제에서 주의할 점은, (나도 이걸로 틀렸다..)
시작 도시 A와 도착도시 B를 연결하는 간선이 여러 개일 수 있다는 점이다.
=> 그럼 가장 최소값만 고려해주면 됨.
예를 들어
A => B 간선 비용 3,
A=> B 간선 비용 5일 때,
A=> B 간선미용 3만 고려해주면 된다는 뜻이다.
도시의 개수 N이 100이하의 정수다. 어떤 생각이 드는가?
플로이드 워셜 알고리즘을 이용하는 것이 효과적이겠다!
- 시간 복잡도 O(n^3) 이지만, 입력값이 작으니 충분하다.
- 해당 노드에 대해서 모든 노드에 대한 최솟값거리를 구할땐, 플로이드 와샬 알고리즘 사용하기
플로이드 와샬 알고리즘을 모르는 분들을 위해 간단하게 설명해보자면, (실제로 간단하다)
노드가 1~3이 있을 때 경우를 가정
1. 먼저, 2차원 배열을 생성한다.
2. 모든 값을 INF로 채운다.
3. 자기 자신으로 가는 노드는 0으로 값을 갱신한다.
- 당연히 1노드에서 1노드로 가는 건 0이다.
4. 문제에서 주어진 간선 비용으로 그래프를 다시 초기화 한다.
- 문제에서 이렇게 주어졌다고 치고 그래프를 초기화해줬다.
1 => 2 ,거리: 1
1 => 3 ,거리: 2
2 => 1, 거리: 3
2 => 3, 거리: 4
3 => 1, 거리: 5
3 => 2, 거리: 6
5. 플로이드 와샬 알고리즘 점화식으로 그래프롤 UPDATE 해준다.
1) 1를 무조건 지나치고 가는 경우
2) 2를 무조건 지나치고 가는 경우
3) 3을 무조건 지나치고 가는 경우
이 세가지 경우를 다 확인해주면서 최솟값으로 그래프를 갱신해주는 것이다.
예시)
1을 무조건 지나치는 경우이면서,
2노드에서 3노드로 갈 때, 값을 갱신해보자.
원래 2노드 => 3노드는 거리 비용이 4이다.
만약 1 노드를 무조건 지나쳐야 한다면?
(2노드 => 1노드) + (1노드 => 3노드) 가 될 것이다.
3 + 2 = 5
5가 된다.
기존의 거리 비용 4보다 크니, 갱신하지 않아도 된다.
만약 기존 거리 비용 4보다 작다면, 그 값으로 값을 채워준다.
정답 코드
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한 의미 10억
# 노드의 개수 및 간선 개수 입려받기
n = int(input())
m = int(input())
# 2차원 리스트를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n+1) for _ in range(n+1)]
# 자기 자신에서 자기 자신으로 가는 비용을 0으로 초기화
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, input().split())
# 가장 짧은 간선 정보만 저장
if graph[a][b] > c:
graph[a][b] = c
# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
# 출력
for i in range(1, n+1):
for j in range(1, n+1):
# 도달할 수 없는 경우, 0출력
if graph[i][j] == INF:
print(0, end=" ")
# 도달할 수 있는 경우 거리 출력
else:
print(graph[i][j], end=" ")
print() # 'print()'가 들여쓰기 조심