백준 1956번 - 운동

운동 문제 바로 가기

풀이 날짜: 2026-01-15

baekjoon 알고리즘 문제 풀이

풀이 코드


import sys
input = sys.stdin.readline

INF = int(1e9)

v,e = map(int, input().split())
dist = [[INF] * (v+1) for _ in range(v+1)]

for _ in range(e):
    a,b,c = map(int, input().split())
    if c < dist[a][b]:
        dist[a][b] = c

for k in range(1,v+1):
    dist_k = dist[k]

    for i in range(1,v+1):
        dist_i = dist[i]
        if dist_i[k] == INF:
            continue

        for j in range(1,v+1):
            if dist_k[j] == INF:
                continue

            new_dist = dist_i[k] + dist_k[j]
            if new_dist < dist_i[j]:
                dist_i[j] = new_dist

answer = min(dist[i][i] for i in range(1,v+1))
print(-1 if answer == INF else answer)

print(count)

문제 핵심 요약:

“출발한 마을로 다시 돌아오는 최소 비용 사이클”을 찾는 문제다. 즉, 최단거리 자체가 아니라 최단 사이클이 목표다. 시작점이 정해져 있지 않고 어떤 정점에서든 출발할 수 있기 때문에, 한 번의 다익스트라/벨만–포드로 끝나는 구조가 아니다. 결국 “모든 정점 쌍의 최단거리”를 구해놓고 그 결과에서 사이클을 뽑는 방식이 가장 자연스럽다.

dist 행렬

이 문제는 dist[i][j]를 “i에서 j로 가는 최단거리”로 두면 풀이가 깔끔해진다. 입력은 방향 그래프이므로 dist[a][b] = c로 초기화하고, 같은 방향의 간선이 여러 개 들어올 수 있으니 min으로 더 작은 비용만 남긴다. 여기서 중요한 점은 이 문제에서 최종적으로 우리가 원하는 건 “사이클”이므로, 플로이드가 끝난 후 dist[i][i] 값이 “i에서 출발해서 i로 돌아오는 최소 비용”이 된다.

플로이드–워셜

3중 루프의 의미는 단순히 “다 돌린다”가 아니라, k를 경유지로 허용했을 때 i → k → j 경로가 더 짧아지는지 확인하는 과정이다.

k : 경유지
i : 출발지
j : 도착지

그리고 매번 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 형태로 갱신한다.

시간초과를 겪으면서 알게 된 “파이썬 플로이드의 현실”

플로이드는 이론적으로 O(v^3)이라 v가 400만 돼도 연산량이 상당하다. 파이썬에서는 단순한 3중 for문만으로는 간당간당하거나 TLE가 나는 경우가 많다.

내가 적용한 최적화 포인트 1: 행(row) 캐싱

시간을 줄이기 위해 dist_k = dist[k], dist_i = dist[i]처럼 행 자체를 변수로 받아오는 캐싱을 했다. 이러면 dist[i][j]처럼 매번 2중 인덱싱을 하는 대신, dist_i[j] 같은 1중 인덱싱으로 접근할 수 있어 파이썬에서 성능이 확 좋아진다. 실제로 플로이드 파이썬 최적화는 대부분 “행 캐싱”이 핵심이다.

내가 적용한 최적화 포인트 2: INF인 경우 continue로 가지치기

i → k가 불가능하면 i → k → j는 애초에 성립하지 않음
k → j가 불가능해도 마찬가지

즉, 불가능한 경로는 더할 필요가 없으니 스킵해서 연산량을 줄인다. 플로이드를 파이썬으로 구현할 때는 이런 가지치기가 거의 필수로 느껴졌다.

Vienna sausage