https://www.acmicpc.net/problem/1719
1719번: 택배
명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하
www.acmicpc.net
💡 접근 방법
문제에서 주어진 그래프만 보고 바로 플로이드 워셜 풀이법을 생각해냈다.
💖 플로이드 워셜
플로이드 워셜이란 모든 노드에서 다른 모든 노드까지의 최단 거리를 계산하는 알고리즘으로
a에서 b까지 가는 최단경로를 찾을 때, min(a -> b까지의 거리, a -> k + k -> b까지의 거리) 값을 구해 최단경로로 설정해주면 된다.
즉, 수식으로 나타내면 아래와 같다.

다익스트라 알고리즘처럼 단계별로 거쳐가는 노드를 기준으로 최단거리를 계산하지만 차이점이 있다.
다익스트라 알고리즘은 매 단계별 방문하지 않은 노드를 찾아서 최단 경로를 검색하고,
플로이드 워셜 알고리즘은 매 단계마다 모든 노드를 계산해준다.
* 플로이드 워셜에 대한 설명은 이 유튜브에 자세히 설명되어 있으므로, 개념을 모른다면 꼭 참고하는것을 추천한다.
다시 문제로 돌아가서 이 문제는 플로이드 워셜 알고리즘과 약간 다른점이 존재했다. 플로이드 워셜 알고리즘은 최단 경로를 기록하는 대신, 이 문제에선 최단 경로일 때 가장 먼저 방문하는 노드의 번호를 기록해야 한다는 점이 달랐다.
그래서 처음 경로를 입력 받을 때, 경로를 담는 graph와 지나는 지점을 기록하는 res 배열 두 개를 만들어서 구현을 해주었다. 근데 여기서 실수를 했던게 나는 graph[a][b] > graph[a][k] + graph[k][b] 인 경우에만 res[a][b]를 방문점으로 변경해주면 된다라고 생각했다.
하지만 아무곳을 거치지 않고 바로 도착하는 경우라면, 도착점이 가장 먼저 방문하는 노드이므로 res[a][b] = b 로 기록을 해줘야 했다.
즉, 예를 들어 아래 그림과 같이 노드 1 -> 노드 2로 이동하는 최단 경로는 다른 점을 거치지 않고 바로 노드1에서 노드2로 가는 방법뿐이다. 이럴 때 res[1][2]의 값은 2(거리값이 아닌 2번 노드라는 의미)가 된다는 뜻이다.
이 부분만 유의해서 플로이드 워셜 알고리즘 방법대로 구현해주면 문제를 쉽게 풀어갈 수 있다.
🔥 문제 풀이
1️⃣ graph를 입력받을 때, res도 함께 입력 받아 준다. -> 처음 입력 받을 땐 위에서 설명한 대로 도착점을 res에 넣어준다.
2️⃣ 플로이드 워셜 알고리즘 기본 코드를 작성해, 만약 graph[a][b] > graph[a][k] + graph[k][b] 가 된다면 graph[a][b]의 값을 graph[a][k] + graph[k][b]로 변경해주고, res[a][b]의 값을 res[a][k]로 변경해준다. (가장 처음 방문하는 점을 기록해야 하기 때문이다)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
graph = [[INF] * (n + 1) for _ in range(n + 1)]
res = [[INF] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
a, b, c = map(int, input().split())
graph[a][b] = c
graph[b][a] = c
res[a][b] = b
res[b][a] = a
for i in range(1, n + 1):
graph[i][i] = 0
res[i][i] = INF
for k in range(1, n + 1):
for a in range(1, n + 1):
for b in range(1, n + 1):
if graph[a][b] > graph[a][k] + graph[k][b]:
graph[a][b] = graph[a][k] + graph[k][b]
res[a][b] = res[a][k]
for i in range(1, n + 1):
for j in range(1, n + 1):
if res[i][j] == INF:
res[i][j] = '-'
for i in res[1:]:
print(*i[1:])
|
cs |
'💻 알고리즘 > 백준' 카테고리의 다른 글
[ 백준 ] 1941 소문난 칠공주 (python) (0) | 2022.11.03 |
---|---|
[ 백준 ] 11967 불켜기 (python) (2) | 2022.11.02 |
[ 백준 ] 1477 휴게소 세우기 (python) (0) | 2022.09.15 |
[ 백준 ] 11657 타임머신 (python) (0) | 2022.06.19 |
[ 백준 ] 16932 모양 만들기 (python) (0) | 2022.06.11 |