[python] 백준 11657 : 타임머신

장선규·2022년 3월 4일
0

알고리즘

목록 보기
30/40

문제 링크
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번의 순회 끝에 한 번 더 모든 간선들에 대하여 값의 갱신을 시도한다. 만일 이 때에도 값의 갱신이 이루어졌다면, 음의 싸이클이 존재하는 것이다.
(총 정점의 개수보다 더 많은 정점을 탐색했다고 생각하자)

따라서 알고리즘은 다음과 같다.

  1. 출발 정점 설정
  2. 각 정점들에 도달하기까지 필요한 최소비용 dist[]inf(매우 큰 수)로 초기화
  3. 다음 과정을 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])
profile
코딩연습

0개의 댓글