[백준]1865 웜홀(Python)

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

1865번: 웜홀

 

문제 접근 

 

도로와 달리 웜홀의 경우 시간이 거꾸로 가기 때문에 음수 간선이 존재할 수 있다.

음수 간선이 존재하므로 벨만-포드 알고리즘을 이용한다. 

 

벨만-포드의 시간 복잡도: O(VE)

 

코드

import sys

input = sys.stdin.readline
INF = sys.maxsize

def bellman_ford(start):
    dist[start] = 0  # 시작 노드에 대하여 초기화

    # N번의 라운드를 반복
    for i in range(1, N+1):
        # 매 라운드마다 모든 간선을 확인
        for j in range(2*M+W):
            now, next, cost = edges[j][0], edges[j][1], edges[j][2]
            # dist[now] != INF => 현재 노드가 시작 노드에서 도달 가능한 노드인 경우
            if dist[next] > dist[now] + cost:   # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧을 경우
                dist[next] = dist[now] + cost
                # N번째 라운드에서도 값이 갱신된다면 음수 순환 존재
                if i == N:
                    return True

    return False

TC = int(input())

for _ in range(TC):
    # 지점수, 도로수, 웜홀수
    N, M, W = map(int, input().split())
    edges = []
    # 최단 거리 테이블을 모두 무한으로 초기화
    dist = [INF] * (N + 1)
    # 도로 정보(양방향)
    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))

    negative_cycle = bellman_ford(1)

    if negative_cycle:
        print("YES")
    else:
        print("NO")

 

문제 회고

 

초반에 자꾸 예제를 넣으면 NO, YES가 아니라 NO, NO가 출력되었다.

우선 저 이중 반복문에서 j의 경우 2*M+W의 횟수만큼 반복이 돌아야 하는 것을 주의하고,

벨만-포드 알고리즘을 이용했던 문제인 타임머신의 경우 dist[now] != INF라는 조건이 필요하지만 해당 문제에서는 시작점이 정해져있지 않아 필요 없으므로 코드 작성에 주의해야 한다.