[Baekjoon] 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을 출력한다.

예제 입력 1

3 4
1 2 4
1 3 3
2 3 -1
3 1 -2

예제 출력 1

4
3

예제 입력 2

3 4
1 2 4
1 3 3
2 3 -4
3 1 -2

예제 출력 2

-1

예제 입력 3

3 2
1 2 4
1 2 3

예제 출력 3

3
-1

출처

• 어색한 표현을 찾은 사람: alex9801, myungwoo, rim
• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: djm03178, doju, ganghe74

알고리즘 분류

• 그래프 이론
• 벨만–포드

문제 풀이

# Graph # ShortestPath # Bellman-ford

Graph 자료구조와 ShortestPath 알고리즘 중 Bellman-ford 알고리즘을 사용하는 문제입니다.

풀이 과정

음수 가중치가 있는 그래프 문제이기 때문에 벨만포드 알고리즘을 사용합니다. 문제의 요구 사항은 아래와 같습니다.

• 1번 도시에서 다른 도시들로 가는 최단거리를 구하라
• 만약 음수 사이클이 있다면 -1을 출력하라
• 해당 도시로 가는 경로가 없다면 최단거리로 -1을 출력하라

벨만포드 알고리즘은 아래와 같이 동작합니다.

1. 시작 정점을 결정한다.
2. 시작 정점에서 각각 다른 정점까지의 거리 값을 무한대로 초기화한다. (시작 정점이 a라면, distance[b] = a->b의 거리를 뜻함) 시작 정점 -> 시작 정점은 0으로 초기화한다.
3. 현재 정점에서 모든 인접 정점들을 탐색하며, 기존에 저장되어 있는 인접 정점까지의 거리(distance[a])보다 현재 정점을 거쳐 인접 정점에 도달하는 거리가 더 짧을 경우 짧은 거리로 갱신해준다.
4. 3번의 과정을 V-1번 반복한다.
5. 위 과정을 모두 마치고 난 후 거리가 갱신되는 경우가 생긴다면 그래프에 음수 사이클이 존재한다는 것이다.

참조: 최단 경로 - 벨만포드 알고리즘

위 과정을 거치고 나면 시작 정점에서 다른 정점으로의 최단 거리를 얻거나, 그래프 내에 있는 음수 사이클의 존재성을 알 수 있습니다.

이 때 음수 사이클이란 만약 A -> B -> C -> A 의 경로가 있을 때 모든 간선의 가중치가 음수라는 뜻은 아닙니다. A -> B 의 가중치가 -10이고 B->C와 C->A 의 가중치의 합이 10 미만이라면 이것 또한 음수 사이클입니다.

즉, 음수 사이클이란 거리(또는 시간, 즉 경로 상의 가중치들의 합)를 무한히 음수로 만들 수 있는 경우를 뜻하고, 이 경우에는 다른 정점으로의 최단 거리를 얻을 수 없음을 뜻합니다.

따라서, 음수 가중치가 있는 경우 방향 그래프가 주어져야 합니다.

전체 코드

import sys
input = sys.stdin.readline
INF = float('inf')

def bellman_ford(startV):
    c,c[startV] = [INF for _ in range(N+1)],0
    for it in range(N):             # 갱신 횟수 제한
        for cv in graph.keys():     # 각 정점에 대하여,
            if c[cv] == INF: continue # 현재 정점으로의 방문이 한 번도 이루어지지 않았다면 갱신을 하지 않는다.
            for nc,nv in graph[cv]: # 현재 정점과 인접한 정점들의 최단거리 갱신
                tmp_c = c[cv] + nc
                if tmp_c < c[nv]:
                    c[nv] = tmp_c
                    if it >= N-1: return -1 # 최단 거리가 N번 이상 갱신된다면 음수 사이클에 갖힌 것 
    return c

N,M = map(int,input().split())
graph = {i+1:[] for i in range(N)}
for _ in range(M):
    A,B,C = map(int,input().split())
    graph[A].append((C,B)) # 방향 그래프
ans = bellman_ford(1)
if ans == -1: print(-1)
else: 
    for c in ans[2:]: print(c if c < INF else -1)

배운 점

• 음수 가중치가 있는 경우 벨만포드 알고리즘을 사용한다.
  • 음수 가중치를 가지는 간선은 방향을 가지고 있어야만 한다.
• 벨만포드 알고리즘의 동작 방식을 알았다.
• 음수 사이클의 개념을 알았다.