[baekjoon] 백준 1865번 : 웜홀 (by python 파이썬) 벨만 포드(Bellman-Ford) 알고리즘

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

1865번: 웜홀

 

정답 code

#웜홀
import sys
input = sys.stdin.readline
INF = int(1e9)

def bellma_ford(start):
    visit = [INF]*(n+1)
    visit[start] = 0
    #정점 개수만큼 반복
    for i in range(n):
        for j in range(1,n+1):
            for next_node , time in roads[j]:
            #다음노드에 저장되있는 비용보다 최단거리라면 갱신
                if visit[next_node] > time + visit[j]:
                    visit[next_node] = time + visit[j]
                    #n번 반복이후에도 갱신이 발생하면 음의 사이클 존재
                    if i == n -1: 
                        return True
    return False

tc = int(input()) #test case
for _ in range(tc):
    n,m,w = map(int,input().split())
    roads = [[] for _ in range(n+1)]
    #도로 입력
    for _ in range(m):
        s,e,t = map(int,input().split())
        roads[s].append((e,t))
        roads[e].append((s,t))
    #웜홀 입력
    for _ in range(w):
        s,e,t = map(int,input().split())
        roads[s].append((e,-t))

    result = bellma_ford(1)
    if result:
        print("YES")
    else:
        print("NO")

 

solution

처음엔 다익스트라를 이용해 풀려 하였다.

아무리 해도 오류가 계속 나와 찾아봤는데 다익스트라알고리즘은 간선의 이동시간이 음수가 있는 경우에는 사용할 수 없다.

따라서 벨만포드 알고리즘을 이용해야했다.

 

아래 블로그에 벨만포드에 대한 내용이 나와있다.

https://velog.io/@younge/Python-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9CBellman-Ford-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[Python] 최단 경로 - 벨만 포드(Bellman-Ford) 알고리즘 구현하기

 

처음 써보는 알고리즘이였지만 다른 최단 경로 알고리즘과 유사한 점이 많아 그렇게 어렵지는 않았다.

다만 생각해야 될 점은 모든지점을 출발지점으로 지정해 찾아보지 않아도 음수 사이클이 존재하는지 찾을 수 있다는 것이다.

 

벨만포드 알고리즘프로세스를 한번 마치고도 갱신이 생긴다면 그래프에 음수사이클이 존재한다는 뜻임으로 True를 반환해 문제를 해결 할 수 있다.