[백준]11657 타임머신 - Python 파이썬

문제

 

 

 

처음에 이 문제를 보고 떠오른 알고리즘은 union-find 그리고 다익스트라였다.

 

하지만 문제가 잘 풀리지 않아 구글링을 해본 후 벨만포드 알고리즘이라는 것을 알게되었다.

 

 

참고 자료: https://velog.io/@mjieun/Algorithm-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Bellman-Ford-algorithm-Python

[Algorithm] 벨만-포드 알고리즘(Bellman-Ford algorithm) - Python

 

 

 

 

 

벨만 포드 알고리즘이란

 

• 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색
• 음수 가중치 에지가 있어도 수행할 수 있음
• 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음
• 시간 복잡도 O(VE) (V: 노드 수, E: 에지 수)

 

 

다익스트라와 차이점은 v-1번 반복 하는 것이 아닌 v번 반복을 통해 마지막 v번째에서 값이 갱신되는 경우 음수 사이클이 존재해서 값이 무한히 줄어드는 경우이기때문에 이 부분에 대한 처리를 따로 해주어야 된다는 점이다.

 

 

 

n,m = map(int,input().split())
INF = int(1e9)
dist = [INF] * (n+1)

edges = []

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

def bf(start):
    dist[start] = 0
    for i in range(n):
        for j in range(m):
            now = edges[j][0]
            nxt = edges[j][1]
            time = edges[j][2]
            if dist[now] != INF and dist[nxt] > dist[now] + time:
                dist[nxt] = dist[now] + time
                #음수사이클 존재여부 확인
                if i == n-1:
                    return True
    return False

minus_cycle = bf(1)

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

 

 

 

벨만 포드 라는 알고리즘을 알고 있지 않으면 해결하기 어려웠던 문제였다. 다익스트라 문제는 기존에 많이 풀었지만 벨만 포드 알고리즘은 처음 접해서 구글링의 도움을 받았다..