[코딩테스트][백준] 🔥 백준 1865번 "웜홀" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 40분

import sys
input=sys.stdin.readline

INF=int(1e9)

def bellmanford(start):
    distance[start]=0
    for i in range(n):
        for edge in edges:
            s,e,v=edge
            if distance[s]+v<distance[e]:
                distance[e]=distance[s]+v
                if i==n-1:
                    return True
    return False

for _ in range(int(input())):
    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))
    
    distance=[INF]*(n+1)
    if bellmanford(1):
        print("YES")
    else:
        print("NO")

웜홀과 음의 간선 탐지! 🌌🔄

웜홀을 통하는 길을 사용할 때는 음의 간선이 처리가 되어서 이 때의 음의 순환이 일어나는지 물어보는 문제이기 때문에 벨만-포드 알고리즘을 사용하면 된다. 시간복잡도도 $O(NxM)$이기 때문에 충분히 가능하다. 벨만-포드 알고리즘을 여기서 처음 다루어보았다.

단순히 모든 지점에 대해 경로를 전부 탐색하여 갱신해주는 문제이기 때문에 시작지점과 관련이 없이 모든 경로가 갱신이 된다. 즉, 시작지점부터의 최단거리로 갱신은 되지만 음의 순환여부는 모든 간선으로 갱신이 되기 때문에 v번째 또 갱신되는 곳을 찾으면 되어서 이와 관련이 없이 갱신이 된다. 그렇기에 v번째, 즉 n번째에도 거리가 갱신되는 곳이 있다면 YES를 없다면 NO를 반환하면 된다.

이렇게 Python으로 백준의 "웜홀" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊