문제 링크
https://www.acmicpc.net/problem/11657
접근
N과 M이 둘 다 크지 않으므로 O(N^3)이나 O(NM) 등 널널하다.
그래프에서 음의 가중치를 가진 간선이 존재하고, 음의 싸이클을 판별해야 하는 문제이므로 벨만-포드 알고리즘을 사용하였다.
벨만-포드 알고리즘
예전에 공부를 했었던 알고리즘인데, 오랫동안 써먹질 않아 기억이 흐릿해져서 다시 공부를 하였다...
다익스트라 알고리즘
다익스트라 알고리즘을 생각해보면, 출발 정점에서부터 시작하여 갈 수 있는 정점들을 탐색해가며 이동한다. 그 과정에서 출발 정점을 제외하고 n-1번의 정점을 방문하게 된다 (n은 정점의 개수).
다익스트라 알고리즘은 그리디하기 때문에 이 n-1번 탐색하는 것에 크게 주의를 기울이지 않아도 된다. 매번 최소의 비용이 드는 간선을 택하기 때문이다. 즉, 다익스트라 알고리즘에서는 이미 방문했던 정점의 값이 갱신되는 일이 없다는 것이다.
벨만-포드 알고리즘
하지만 음의 가중치가 있는 그래프는, 이미 방문했던 정점으로 가는 최솟값이 갱신될 수 있다.
(극단적으로 음의 싸이클을 무한히 돌아버리면 모든 정점으로 가는 비용이 -inf가 될 수도 있는 것이다.)
이를 방지하기 위해, 벨만-포드 알고리즘은 시작점에서 출발하여 "모든 간선"들에 대하여 n-1번 순회를 한다.
이러한 방법은, 음의 싸이클이 존재해도 각 정점으로 가는 비용이 무한히 줄어들지 않는다는 장점이 있다. (n-1번 순회하는 조건이 없다면, 음의 싸이클이 무한히 갱신되어 해당 정점들로 가는 비용이 무한히 줄어든다)
하지만 여기까지만 하면 음의 싸이클이 있는지 명확하게 알지 못한다.
음의 싸이클의 존재 여부를 확인하려면 n-1번의 순회 끝에 한 번 더 모든 간선들에 대하여 값의 갱신을 시도한다. 만일 이 때에도 값의 갱신이 이루어졌다면, 음의 싸이클이 존재하는 것이다.
(총 정점의 개수보다 더 많은 정점을 탐색했다고 생각하자)
따라서 알고리즘은 다음과 같다.
- 출발 정점 설정
- 각 정점들에 도달하기까지 필요한 최소비용
dist[]를inf(매우 큰 수)로 초기화- 다음 과정을 n-1번 반복
3-1 모든 간선 e를 확인
3-2 만약 해당 간선을 지나갈 수 있고 최소 비용을 비교하여, 비용이 더 작다면 갱신한다.
풀이
MAX = 100000000
n, m = map(int, input().split())
dist = [MAX for _ in range(n + 1)]
edge = [tuple(map(int, input().split())) for _ in range(m)]1,2번에 해당한다. 출발 정점은 1로 고정이기 때문에 생략.
def bf(): # bellman-ford
dist[1] = 0
for i in range(n): # n-1 번 돌고, 마지막 n번째에는 갱신되면 음의 싸이클 있는지 보는 것
for e in edge:
frm, to, cost = e
if dist[frm] != MAX and dist[to] > dist[frm] + cost:
dist[to] = dist[frm] + cost # 값 갱신
if i == n - 1: # 만약 n번째 시도에도 값 갱신됐으면
return 1 # 음의 싸이클 존재
return 0 # 음의 싸이클 존재하지 않음3번에 해당한다.
모든 정점들을 탐색하고 갱신하는 작업을 n-1번 반복한다.
n-1번 반복이 끝났으면 모든 정점에 대하여 순회를 했다고 보면 된다.
그리고 마지막으로 음의 싸이클이 존재하는지 알아보기 위해 한 번 더 탐색한다.
만약 이번에도 값 갱신이 이루어졌다면, 음의 싸이클이 존재하는 것이다. 참을 반환해준다.
값 갱신이 이루어지지 않았으면, 음의 싸이클이 없는 것이다. 언제부터인지는 모르겠지만 어느 순간부터는 값 갱신이 일어나지 않은 것이다! 이 경우 어떤 방법을 써도 값이 계속해서 줄어드는 일은 일어나지 않는 것이다.
정답 코드
import sys
input = lambda: sys.stdin.readline().rstrip()
MAX = 100000000
n, m = map(int, input().split())
dist = [MAX for _ in range(n + 1)]
edge = [tuple(map(int, input().split())) for _ in range(m)]
def bf(): # bellman-ford
dist[1] = 0
for i in range(n): # n-1 번 돌고, 마지막 n번째에는 갱신되면 음의 싸이클 있는지 보는 것
for e in edge:
frm, to, cost = e
if dist[frm] != MAX and dist[to] > dist[frm] + cost:
dist[to] = dist[frm] + cost # 값 갱신
if i == n - 1: # 만약 n번째 시도에도 값 갱신됐으면
return 1 # 음의 싸이클 존재
return 0 # 음의 싸이클 존재하지 않음
if bf():
print(-1)
else:
for i in range(2, n + 1):
print(-1 if dist[i] == MAX else dist[i])
