[탐색/밸만포드] 백준 1865 웜홀 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1865번: 웜홀

 

 

 

2. 문제 풀이

 음수 가중치를 갖는 사이클(음수 사이클)이 있는 지 탐색하는 문제입니다. 

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 밸만 포드 알고리즘
def bf(start):
    dist = [10001] * (N + 1)
    dist[start] = 0

    # 밸만포드 알고리즘
    for i in range(N):
        for e in edge:
            start_node, next_node, cost = e

            # 최단거리로 갱신 가능한 경우
            if dist[start_node] != 10001 and dist[next_node] > cost + dist[start_node]:
                dist[next_node] = cost + dist[start_node]
                if i == N-1:
                    return True
    return False

TC = int(input())
for _ in range(TC):
    N, M, W = map(int, input().split())  # 노드, 간선, 웜홀의 수
    edge = []
    for _ in range(M):
        s, e, t = map(int, input().split()) # 출발, 도착지, 걸리는 시간
        edge.append((s, e, t))
        edge.append((e, s, t))
    for _ in range(W):
        s, e, t = map(int, input().split())  # 출발, 도착지, 줄어드는 시간
        edge.append((s, e, -t))  # 출발, 도착, 줄어드는 시간

    # 밸만포드 알고리즘으로 음의 사이클 확인
    # 1 ~ n번 노드까지 음의 사이클이 있는지 판별
    for i in range(1, N+1):
        if bf(i):
            print("YES")
            break
    else:
        print("NO")

 밸만 포드를 이용해도, 파이썬의 장벽에 부딪혀 시간초과가 납니다. 이런 걸 생각하면 C++이 사기이긴 하네요.

 

What’s New In Python 3.11 — Python 3.11.0b1 documentation

(3.11이 빨리 배포되길 기원합니다. 3.10보다 10% ~ 60까지 빠르다고 합니다.)

 

정답 풀이 (코드)

dist[10001] 초기화까지 포기해야 통과한다고 합니다.