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

문제

https://www.acmicpc.net/problem/11657

11657번: 타임머신

---

문제 요약

N개의 도시가 있다. 그리고 한 도시에서 다른 도시에 도착하는 버스가 M개가 있다.

 

각 버스는 시작 도시 A, 도착 도시 B, 걸리는 시간 C로 나타낼 수 있다.

+ C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

 

버스 노선의 정보가 주어질 때, 1번 도시에서 출발해 나머지 도시로 가는 가장 빠른 시간대를 출력한다.

---

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
# n은 도시 개수, m은 버스 노선 개수

graph = []

MAXNUM = sys.maxsize

dist = [MAXNUM] * (n + 1)  # dist[i]는 1번 도시에서 i번 도시로 가는 가장 빠른 시간 (초기: 무한대)
dist[1] = 0 # 시작점 (1번 도시)

for _ in range(m):
    start, end, w = map(int, input().split()) # start -> end 가중치 w
    graph.append((start, end, w))

for _ in range(n):
    for start, end, w in graph:
        if dist[start] != sys.maxsize:
            distance = dist[start] + w
            if distance < dist[end]:
                dist[end] = distance

# 그래프에 음의 사이클이 있는지 판별        
flag = False
for start, end, w in graph:
    if dist[start] != sys.maxsize:
        distance = dist[start] + w
        if distance < dist[end]:
            flag = True

if flag:
    print(-1)
    sys.exit()
    
for i in range(2, n + 1):
    if dist[i] == MAXNUM:
        print(-1)
        continue
    print(dist[i])

---

코드 설명

그래프의 가중치에 음수가 있을 수 있으므로, 벨만 포드 알고리즘을 이용한다.

 

1. 2차원 배열 graph에 버스 노선 정보를 저장한다.

 

2. 1번 도시에서 i번 도시로 가는 가장 빠른 시간을 저장하는 배열 dist를 생성한다.

+ 초기: 1번 인덱스 = 0, 나머지 = 무한

 

3. graph에 있는 정보를 n번 확인하며 dist를 갱신한다.

 

4. n + 1번 확인했을 때, dist가 갱신된다면, 음수인 사이클을 갖고 있다는 의미이다.

 

5. 나머지 도시로 가는 가장 빠른 시간대를 출력한다.