99클럽 코테 스터디 29일차 (BOJ 11657 타임머신)

오늘의 문제: BOJ 11657(타임머신)

문제 설명

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

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

만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다.

 

문제 해결

첫 주차에 공부했던 벨만-포드 알고리즘을 사용하여 해결하였습니다. 

벨만-포드 알고리즘이란

• 벨만-포드 알고리즘
  • 특정 시작 노드로 부터 모든 다른 노드까지의 최단 거리 계산 알고리즘
  • 최단 경로 계산 과정
    • 벨만-포드는 그래프의 모든 간선을 최대 n-1번 반복하여 최단 경로를 갱신
    • 시작점으로부터 다른 노드로 가는 최단 경로가 n-1개의 간선을 거칠수 있다는 원리에 기반
  • 음의 가중치 사이클 탐지
    • 만약, n-1번 반복이후 한번더 반복해서 최단 거리가 갱신, 이는 음의 가중치 사이클이 존재
    • 음의 가중치가 있는경우 사이클을 반복하는 동안 음의 가중치가 최단거리가 되어 계속 더해지므로
    • 정상 적인 그래프는 n-1번 반복 이후 더 이상 갱신이 발생하지 않음

위의 조건에 맞게 음의 사이클 발견시 -1을 출력 음의 사이클이 아닐시에는 1에서 출발하여 각 노드로 도착하는 최단 시간을 출력해 주었습니다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, cost = map(int, input().split())
    graph[a].append((b, cost))

INF = float('inf')

dp = [INF for _ in range(n+1)]
dp[1] = 0
bellman = False

for i in range(n):
    updated = False
    for u in range(1, n+1):
        for v, time in graph[u]:
            if dp[v] > dp[u] + time:
                dp[v] = dp[u] + time
                updated = True
                if i == n -1:
                    bellman = True
                    
    if not updated:
        break
if bellman:
    print(-1)
else:
    for i in range(2, n+1):
        if dp[i] == INF:
            print(-1)
        else:
            print(dp[i])