[Python] 백준 1865 : 웜홀 (Bellman Ford)

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

머리말

문제를 보고, 아 negative cycle 찾는 문제이구나 싶었다.

 

그래프에서 최단 경로를 탐색하는 방법 중 다익스트라와 벨만 포드가 있는데,
다익스트라는 Greedy 알고리즘이기 때문에 반드시 간선들이 non-negative weights을 만족해야 한다.
한편, 벨만 포드는 Dynamic Programming 알고리즘으로 negative weights를 가져도 정상적으로 동작한다!

 

접근 방법

고급문제해결 수업 자료

• edge relaxation을 N-1번 수행한다.
• 그때 만들어진 distance 배열은 최단 경로이다.
• edge relaxation을 N번째 수행했을 때, 더 짧은 경로를 발견한다면 negative weight cycle이 존재한다는 결론!

 

이슈 사항

1. 시간 초과

문제에서 시작 정점을 주지 않아, 모든 정점에 대하여 시도하였더니 시간 초과가 발생하였다.

 

결론은 한 정점에서만 시작해도 된다.
벨만 포드 알고리즘에서 한 정점에서부터 다른 정점의 최단 경로를 파악하려고 했기 때문에 방문했던 노드를 다시 방문하지 않으려고 dist[s] != INF라는 조건을 주었다. 하지만 이 문제의 경우 최단 경로를 파악하기 위함이 아닌, just 음수 사이클을 판단하면 된다. (결론적으로 dist 배열은 최단 경로를 저장하는 배열은 아님)

2. 맞왜틀?

처음에 무한대를 float('inf')로 설정하였더니 틀렸다. 대신 int(1e9)로 잡았더니 성공했다.

이것은 dist[s] != INF를 해주지 않았기 때문에 무한대 + 무한대의 계산도 진행된다.
이 과정에서 overflow가 발생할 여지가 충분하므로 잘못된 계산 결과가 나온다.

 

코드

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

def bellman_ford(start):
    dist = [INF] * (n + 1)
    dist[start] = 0

    # n-1 (vertex개수-1) 번 반복
    for i in range(n):
        for j in range(len(edges)):
            s, e, t = map(int,edges[j])

            if dist[e] > dist[s] + t:
                dist[e] = dist[s] + t
                if i == n-1: # n번째에도 존재한다면 음의 cycle 존재
                    return True
    return False

tc = int(input())
for _ in range(tc):
    n,m,w = map(int,input().split())
    edges=[]
    for _ in range(m):
        s,e,t=map(int,input().split())
        edges.append([s, e, t])
        edges.append([e, s, t])
    for _ in range(w):
        s,e,t=map(int,input().split())
        edges.append([s, e, -t])
    print('YES' if bellman_ford(1) else 'NO')

 

더 읽을거리

• https://backtony.github.io/algorithm/2021-02-13-algorithm-boj-class4-10/