[Python] 1865 - 웜홀

[Gold III] 웜홀 - 1865 

[문제 링크](https://www.acmicpc.net/problem/1865)

🗝️알고리즘 분류

• 최단 경로
• 벨만-포드

---

💻문제 정의

N개의 지점이 존재하는 마을에서, 한 지점에서 출발하여 웜홀을 통해 시작 지점으로 돌아왔을 때, 출발 시간보다 이전 시간대로 돌아온 경우 "YES"를 출력하고 아니면 "NO"를 출력하는 문제이다.

 

즉, 주어진 마을을 그래프로 표현하였을 때, 어느 한 정점에서 부터 사이클이 발생하고, 그 사이클이 무한한 음수 사이클을 가지는지를 찾는 문제이다.

 

💡접근 및 설계

사이클 발생 및 음수 여부를 판단하기 위한 알고리즘으로 벨만-포드 알고리즘을 활용한다.

 

 

✏️알고리즘 풀이

def bellman_ford(start):
    # 시작 노드 거리 초기화
    distance[start] = 0
    # 전체 노드 반복
    for i in range(N):
        # 매 반복마다 모든 간선 확인
        for j in range(2*M+W):
            curr_node = edge[j][0]
            next_node = edge[j][1]
            edge_cost = edge[j][2]

            # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 짧은 경우
            if (distance[next_node] > distance[curr_node] + edge_cost):
                distance[next_node] = distance[curr_node] + edge_cost

                # N-1 번째에서 값이 갱신된다면 음수 순환이 존재
                if (i == N - 1):
                    return True

    return False

기존의 벨만-포드 알고리즘을 변형하였다.

 

모든 정점에 대해서 모든 간선을 확인한다. 그리고 각 정점에 대해서 최단 경로를 distance 리스트에 저장한다.

 

이 과정을 N-1번 반복하게 되는데, (N = 정점의 개수) 마지막 반복에서 최단 경로 값에 변화가 생긴다면, 이는 음의 사이클이 존재한다는 뜻이 된다.

 

🗒️전체 코드

# 1865 웜홀

T = int(input())

INF = 1_000_000_000

def bellman_ford(start):
    # 시작 노드 거리 초기화
    distance[start] = 0
    # 전체 노드 반복
    for i in range(N):
        # 매 반복마다 모든 간선 확인
        for j in range(2*M+W):
            curr_node = edge[j][0]
            next_node = edge[j][1]
            edge_cost = edge[j][2]

            # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 짧은 경우
            if (distance[next_node] > distance[curr_node] + edge_cost):
                distance[next_node] = distance[curr_node] + edge_cost

                # N-1 번째에서 값이 갱신된다면 음수 순환이 존재
                if (i == N - 1):
                    return True

    return False

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

    edge = []
    distance = [INF for _ in range(N+1)]

    for _ in range(M):
        S, E, T = map(int, input().split())
        edge.append([S, E, T])
        edge.append([E, S, T])

    # 웜홀 정보 (T가 음수)
    for _ in range(W):
        S, E, T = map(int, input().split())
        edge.append([S, E, -T])

    if bellman_ford(1): # 시작점은 의미 없음
        print("YES")
    else:
        print("NO")

---