벨만 포드 알고리즘 학습을 위해 풀어본 문제이다.
문제풀이
벨만 포드 알고리즘 문제로, 벨만 포드 알고리즘의 자세한 내용은 여기를 참고.
간단히 요약하자면, 노드 수를 n이라 하면, 모든 노드에 대한 relaxation을 n-1번 진행한다. 아래의 코드를 보면 총 3중 for문으로 구성되는데, 첫 번째 for문이 relaxation을 n-1번 진행할 때의 n-1이고, 두 번째 for문이 relaxation을 수행하는 노드이고, 마지막 for문이 relaxation을 수행하기 위한 두 번째 for문의 변수 노드의 이웃 탐사가 된다.
여기서 머리 아픈 문제는 음의 루프가 존재해서 루프를 돌수록 시간이 무한히 과거로 가는 것인데, n-1번의 모든 노드에 대한 relaxation이 모두 이루어지면 더이상 relaxation이 이루어지지 않는다는 점을 활용하여, relaxation을 한번 더 수행하여 relaxation이 일어난다면 음의 루프가 있다고 판정한다.
Python Code
|
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
|
import sys
def bf(n,edge):
INF = 999999999
dist = [0,0] + [INF for _ in range(n-1)]
for count in range(1,n+1):
for a in range(1,n+1):
if dist[a] != INF :
for b,c in edge[a].items():
if dist[b] > dist[a]+c :
dist[b] = dist[a]+c
if count == n:
print(-1)
return
for a in range(2,n+1):
print(dist[a] if dist[a] != INF else -1)
if __name__=="__main__":
n,m = map(int,sys.stdin.readline().split())
edge = {}
for a in range(1,n+1):
edge[a]={}
for _ in range(m):
a,b,c = map(int,sys.stdin.readline().split())
edge[a][b]= min(c,edge[a][b]) if b in edge[a] else c
bf(n,edge)
|
cs |
Line 4 : 1번노드에서 i번 노드까지 걸리는 시간으로, n개의 노드가 1부터 n이므로 0을 사용하지 않기 위해 0번째와 1번째를 0으로 하고 뒤부터는 INF로 초기화한다.
Line 6 : n-1 +1 번 모든 노드에 대한 relaxation을 수행한다고 했는데, relaxation이 몇 회차인지를 나타내는 첫 번째 for문이 된다.
Line 7 : relaxation을 수행하는 노드로 두번째 for문이 된다.
Line 8 : relaxation을 수행하는 노드가 아직 접근할 수 없는 노드이면 relaxation을 수행하지 않는다.
Line 9 : Line 7의 노드의 이웃들을 탐사하는 마지막 for문이 된다.
Line 12 : 음의 루프를 탐사하기 위한 조건으로, n번째에는 relaxation이 일어나면 안 된다.
Line 21 : 링크들이 담겨있는 딕셔너리로, key는 노드 번호이고, value는 (key가 도착 노드, value가 걸리는 시간)인 딕셔너리이다.
문제 링크
11657번: 타임머신
첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.
www.acmicpc.net
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 2884 알람 시계 (0) | 2020.05.08 |
|---|---|
| 백준 9465 스티커 (0) | 2020.04.18 |
| 백준 1002 터렛 (0) | 2020.04.09 |
| 백준 11048 이동하기 (0) | 2020.03.30 |
| 백준 10610 30 (0) | 2020.03.28 |