백준 11657번 - 타임머신

타임머신 문제 바로 가기

풀이 날짜: 2026-01-15

baekjoon 알고리즘 문제 풀이

풀이 코드


import sys
input = sys.stdin.readline

INF = int(1e9)

n,m = map(int, input().split())
data = []
for _ in range(m):
    a,b,c = map(int, input().split())
    data.append((a,b,c))

dist = [INF] * (n+1)
dist[1] = 0

for _ in range(n-1):
    updated = False
    for a,b,c in data:
        if dist[a] != INF and dist[b] > dist[a] + c:
            dist[b] = dist[a] + c
            updated = True
    if not updated:
        break

has_neg_cycle = False
for a,b,c in data:
    if dist[a] != INF and dist[b] > dist[a] + c:
        has_neg_cycle = True
        break

if has_neg_cycle:
    print(-1)
else:
    for i in range(2, n+1):
        if dist[i] == INF:
            print(-1)
        else:
            print(dist[i])
print(count)

문제 핵심 요약:

해결 전략을 세우며 가장 먼저 고민한 것은 “어떤 회의를 먼저 선택해야 이후 선택의 폭이 넓어질까”였다.

이 질문에 대한 답은 회의의 시작 시간이 아니라 끝나는 시간에 있었다. 빨리 끝나는 회의를 먼저 선택할수록 다음 회의를 배치할 수 있는 시간이 많아지고, 그 결과 더 많은 회의를 선택할 수 있다고 판단했다.

이 순간, 이 문제가 그리디 알고리즘이라는 확신이 들었다.

문제 접근

1번 도시에서 출발해 모든 도시까지의 최단 시간을 구하는 문제이다. 간선에 음수 가중치가 존재할 수 있고, 1번 도시에서 도달 가능한 음수 사이클이 있으면 -1을 출력해야 한다. 이 조건 때문에 “단일 시작점 + 음수 간선 + 음수 사이클 판별”이 가능한 벨만-포드 알고리즘을 사용하면 된다.

updated 변수를 둔 이유 (최적화)

한 번의 라운드에서 어떤 거리도 갱신되지 않았다면, 그 이후에도 더 이상 갱신될 일이 없다. 따라서 조기 종료를 통해서 불필요한 반복을 줄이고, 시간 초과를 방지한다. 하지만 이 최적화는 음수 사이클 판별을 대체하진 않는다는 점을 유의하자.

음수 사이클을 따로 검사하는 이유

n-1번의 완화가 끝났다는 것은:

사이클을 쓰지 않는 모든 최단 경로가 반영되었다는 뜻!

하지만 아직 더 줄어드는 간선이 있다면

어떤 사이클을 한 번 더 돌면
거리 값이 계속 감소한다는 의미이다. 즉, 음수 사이클이 존재한다는 것이다.

구현 과정에서 겪은 어려움

① 완화는 한 번으로 끝나지 않는다

완화 1번 = 간선 1개짜리 경로 전달
길이가 긴 경로는 여러 번의 완화가 필요하다.

② updated == False ≠ 음수 사이클 없음

updated는 “이번 라운드에서 변화가 있었는지”만 본다.
음수 사이클 존재 여부는 반드시 별도로 검사해야 한다.

③ 음수 사이클 검사는 “계산”이 아니라 “판정”

dist를 갱신하지 않는다.
“아직 더 줄어들 수 있나?”만 확인한다.