[백준 1865] 웜홀

문제 출처 : https://www.acmicpc.net/problem/1865

1865번: 웜홀

 

웜홀은 시간이 거꾸로 가는 곳입니다. 따라서 최단 경로를 구할 때 음의 가중치를 가진 간선이라 생각하면 됩니다. 이 문제에서는 음의 사이클이 존재하는지 존재하지 않는지 확인하는 문제입니다. 벨만 포드 알고리즘을 사용하여 음의 사이클이 있다면 YES를, 음의 사이클이 없다면 NO를 출력하는 문제입니다. 

다빈치코딩 알고리즘에 벨만포드 알고리즘을 설명해 놓았습니다. 벨만포드 알고리즘을 아직 잘 모른다면 확인해보시기 바랍니다.

함정 확인

이 문제에는 몇가지 함정이 있는데 첫 번째 함정이 도로는 양방향이고, 웜홀은 일방향이라는 것입니다. 따라서 도로는 양쪽 노드 모두 등록해야 하고, 웜홀은 한쪽만 등록하면 됩니다.

두 번째 함정은 웜홀의 가중치가 양수라는 것입니다. 웜홀을 등록할 때 가중치가 음수가 될 수 있도록 바꿔주어야 합니다.

마지막 함정으로 웜홀과 도로가 꼭 연결되어 있다는 보장이 없습니다. 즉 특정 위치에서 벨만 포드 알고리즘을 돌렸을 때 웜홀과 연결이 되어 있지 않아 시간 여행이 되지 않는다고 생각하였지만 다른 위치에서는 시간여행이 가능할 수도 있는 것입니다.

우리는 최단 경로를 구하는 것이 아니라 정점의 개수 - 1번 만큼 경로 업데이트 하고 N번째에도 경로 업데이트가 되는지를 확인하는 문제인 것입니다. 다행인 것은 직접 최단 경로를 구할 필요는 없다는 것입니다.

벨만 포드 알고리즘은 최단 경로를 찾고, 음의 사이클이 있다면 그것을 감지하는 역할을 하지만 여기서는 음의 사이클만을 찾는데 사용하면 됩니다. 그럼 함께 문제를 풀어보도록 하겠습니다.

입력 받기

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    N, M, W = map(int, input().split())

    arr = []
    for _ in range(M):
        s, e, t = map(int, input().split())
        arr.append((s, e, t))
        arr.append((e, s, t))
    
    for _ in range(W):
        s, e, t = map(int, input().split())
        arr.append((s, e, -t))
    
    if bellman_ford():
        print("YES")        
    else:
        print("NO")

테스트 케이스 T를 입력 받고 테스트 케이스에 있는 내용을 입력 받습니다. M개의 도로는 양방향 도로이므로 시작과 끝 노드 두개를 간선에 추가합니다. 다음으로 웜홀은 단양향이기 때문에 하나만 입력합니다. 중요한 점은 웜홀의 시간은 양수로 표현되어 있지만 음수여야 합니다. 따라서 시간 앞에 - 를 추가하여 음수로 전환 합니다.

마지막으로 벨만 포드 알고리즘을 실행하여 음의 가중치가 있으면 True를 리턴하여 YES가 출력되고, 음의 가중치가 없으면 False를 리턴하여 NO가 출력되도록 합니다.

벨만 포드 알고리즘

INF = 10e9

def bellman_ford():
    time = [INF] * (N+1)
    time[1] = 0

    for i in range(N):
        for s, e, t in arr[::-1]:
            next_time = time[s] + t

            if next_time < time[e]:
                time[e] = next_time
                if i == N - 1:
                    return True
    return False

이 문제에서의 벨만포드 알고리즘은 기존의 벨만포드 알고리즘과 다릅니다. 바로 길이가 무한대일 경우 건너뛰는 로직을 삭제하였기 때문입니다. 기존 벨만포드 알고리즘에서는 출발점과 연결되지 않은 정점은 업데이트 되지 않습니다. 하지만 우리는 출발점과는 상관없이 계속적인 업데이트가 일어나는지를 확인하기 위한 것이기 때문에 간선이 있다면 무조건 업데이트를 진행합니다. 그런 이유로 무한대 값을 진짜 무한대인 float(”INF”)가 아닌 계산 가능한 큰 수로 변경한 것입니다. 그 외에는 기존 벨만 포드 알고리즘과 똑같습니다.

최종적으로 음의 사이클이 발견되면 True를 리턴하고, 음의 사이클이 없으면 False를 리턴하게 됩니다.

 

전체코드

전체 코드를 확인해 보겠습니다.

import sys
input = sys.stdin.readline

T = int(input())

INF = 10e9

def bellman_ford():
    time = [INF] * (N+1)
    time[1] = 0

    for i in range(1, N + 1):
        for s, e, t in arr[::-1]:
            next_time = time[s] + t

            if next_time < time[e]:
                time[e] = next_time
                if i == N:
                    return True
    return False

for _ in range(T):
    N, M, W = map(int, input().split())

    arr = []
    for _ in range(M):
        s, e, t = map(int, input().split())
        arr.append((s, e, t))
        arr.append((e, s, t))
    
    for _ in range(W):
        s, e, t = map(int, input().split())
        arr.append((s, e, -t))
    
    if bellman_ford():
        print("YES")        
    else:
        print("NO")