[Python] [백준] 11657번: 타임머신

www.acmicpc.net/problem/11657

11657번: 타임머신

 

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. 

출력

만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

 

풀이

동빈나 님의 코딩 테스트를 위한 벨만 포드 알고리즘 7분 핵심 요약 영상을 참고하였습니다.

youtu.be/Ppimbaxm8d8

음수 간선이 포함된 상황에서 최단 거리를 구하는 문제이다.

음수 간선이 단순하게 포함된 상황이라면 다익스트라 알고리즘으로 풀어도 상관이 없지만, 음수 간선의 순환이 포함되어 있다면 다익스트라 알고리즘을 사용할 수 없게 된다.

이럴 경우 사용하는 것이 벨만 포드 알고리즘이다.

 

n번의 라운드를 반복하며 모든 간선을 최소 거리로 갱신시키고, n번째 라운드에서도 값이 갱신된다면 음수 순환이 존재한다고 판명하는 로직이다.

따라서 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하는 다익스트라 알고리즘에 비해 매번 모든 간선을 확인하는 벨만 포드 알고리즘은 시간 자체는 오래 걸리게 된다.

하지만 음의 순환을 검출할 수 있다는 장점이 있다.

 

 

import sys
input = sys.stdin.readline
INF = int(1e9)


def bellman_ford(start):
    dist[start] = 0

    # n번의 라운드를 반복
    for i in range(1, n + 1):
        # 매 라운드마다 모든 간선을 확인
        for j in range(m):
            now, next, cost = edges[j][0], edges[j][1], edges[j][2]
            # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if dist[now] != INF and dist[next] > dist[now] + cost:
                dist[next] = dist[now] + cost
                # n번째 라운드에서도 값이 갱신된다면 음수 순환 존재
                if i == n:
                    return True

    return False


n, m = map(int, input().split())
edges = []
dist = [INF] * (n + 1)

for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append((a, b, c))

negative_cycle = bellman_ford(1)

if negative_cycle:
    print(-1)
else:
    for i in range(2, n + 1):
        # 도달할 수 없는 경우
        if dist[i] == INF:
            print(-1)
        # 도달 가능한 경우
        else:
            print(dist[i])