[BOJ][Python]11657 풀이

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

11657번: 타임머신

import sys
ssr = sys.stdin.readline

INF = 5000001

def bellman_ford():
    for i in range(n):
        for cur_node, next_node, next_time in routes:
            if min_time[cur_node] != INF and min_time[cur_node]+next_time < min_time[next_node]:
                min_time[next_node] = min_time[cur_node]+next_time
                if i == n-1:
                    return False
    return True
       
n, m = map(int, ssr().split())
routes = [list(map(int, ssr().split())) for _ in range(m)]
min_time = [INF for _ in range(n+1)]
min_time[1] = 0
result = bellman_ford()
if result:
    for i in min_time[2:]:
        if i != INF:
            print(i)
        else:
            print(-1)
else:
    print(-1)

이번에는 벨만-포드 입니다. 약간 선입견이 있었던 것 같아요. 벨만-포드도 시작 노드에서 모든 노드로 가는 최단거리를 구하는 알고리즘이란 걸 알고 있어서 데이크스트라랑 비슷하게 생겼겠구나하고 그런 느낌으로 코드를 짜고 있었는데 좀 다르더라구요. 결국 찾아보고 풀었습니다.

 

벨만 포드의 개념에 대한 내용은 문제도 더 풀어보고 공부도 좀 더 한 다음에 작성하게 될 것 같습니다. 예전에는 각 문제마다 알고리즘에 대한 설명을 달았었는데 확실히 좀 공을 들여서 글 하나를 정리해두고 해당 글을 링크로 걸어두는게 저도 굳이 여러 번 같은 내용을 작성하지 않아도 되고, 보는 분들 입장에서도 좀 더 나은 글을 볼 수 있을 것 같아요.

 

그래도 문제를 간단하게 설명하면, 음의 사이클이 존재하거나 갈 수 없는 노드의 경우는 -1을 출력하고 갈 수 있다면 최단거리를 출력하는 문제입니다. 음의 간선이 입력으로 주어지기 때문에 데이크스트라를 사용할 수 없습니다. 그래서 벨만-포드 알고리즘을 사용해야합니다.

 

벨만-포드 알고리즘의 아이디어는 모든 노드를 다 방문하면서 최단거리를 갱신하는 경우 최대 n-1번의 반복이면 충분하다에서 출발합니다. 간선 정보에 따라 다르겠지만 시작노드에서 출발하여 모든 간선을 다 돌아다니면서 갱신을 한다고 치면 간선의 갯수 m번의 이동으로 다 갱신할 수 있을 겁니다. 하지만 그게 최단거리라는 보장은 절대할 수 없겠죠. 그래서 다른 모든 노드에 대해서도 같은 과정을 반복합니다. 작업이 제대로 이루어졌다면, 마지막 하나의 노드에 대해서는 진행할 필요가 없을 겁니다. 이미 앞에서 모든 경우를 다 시험하고 갱신이 되어있는 값이니까요. 하지만 음의 간선이, 그것도 음의 사이클이 존재한다면 어떨까요? 진행하면 진행할수록 최단거리가 갱신이 될겁니다. '최단거리'니까요. 빼면 뺄수록 값이 줄어들겠죠. 그래서 정상적으로 진행됐다면 이미 최단거리 갱신 작업이 끝나서 더 값이 떨어질 일이 없는데 또 값이 떨어진다고 하면 이건 음의 사이클이 존재하는 거구나 하고 추측할 수 있는 것이죠. 이게 벨만-포드의 핵심 아이디어입니다.

 

그래서 bellman_ford 함수를 확인해보시면 마지막 반복 i가 n-1일 때의 반복에서 최단 거리가 갱신이 된다면 이건 음의 사이클이 존재하네 라고 판단해주는 겁니다.