[백준 1865] 웜홀 - Python 풀이 (골드3)

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

1865번: 웜홀

---

문제 요약

그래프가 주어지는데, 도로는 무방향, 웜홀은 방향이 있는 간선이다. 

그리고 웜홀의 경우 시간(가중치)이 음수라는 특징이 있다.

그래프 정보를 입력 받아서, 한 지점에서 출발해서 다시 돌아왔을 때, 소요 시간이 음수가 되는지를 체크해서 리턴해야 한다.

 

---

풀이

가중치가 음수인 값이 주어지므로 다익스트라 알고리즘은 사용할 수 없다. 다익스트라보다는 느리지만, 이 문제에서 요구하고 있는 '음수 간선 순환 여부'를 탐지할 수 있는 '벨만 포드 알고리즘'을 활용한다. 벨만포드 알고리즘의 작동 순서는 다음과 같다.

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 다음의 과정을 n-1번 반복한다.
  3.1. 전체 간선 e개를 하나씩 확인한다.
  3.2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여, 최단 거리 테이블을 갱신한다.
만약, 음수 간선 순환 발생 여부를 체크한다면 n번 반복한다.
n 번째 반복에서 최단 거리 테이블이 갱신된다면, 음수 간선 순환이 존재한다는 의미이다.

벨만포드 알고리즘은 다익스트라 알고리즘과는 달리, 방문 여부와 상관없이 매번 모든 간선을 확인해야 하기 때문에, 시간 복잡도가 O(VE)가 소요되어, 다익스트라 알고리즘(O(E*logV))보다 더 오래 걸린다(V:정점 수, E: 간선 수). 다만, 가중치가 음수인 경우에도 사용할 수 있고, 음수 간선 순환을 탐지할 수 있다는 장점이 있다.

 

# 백준 1865 웜홀 골드3 https://www.acmicpc.net/problem/1865
# 도로는 무방향, 웜홀은 방향 있음
# 웜홀은 도착 시 시간이 거꾸로 흐름.
# 한 지점에서 출발해서 다시 돌아왔을 때, 출발했을 때보다 시간이 뒤로 갔는지를 체크하는 프로그램

# 벨만 포드 알고리즘
"""
1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 다음의 과정을 n-1번 반복한다. 
    1. 전체 간선 e개를 하나씩 확인한다.
    2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
(만약 음수 간선 순환이 발생하는지 체크한다면 n번 반복한다.)
- n번째 반복에서 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재한다는 의미이다.

다익스트라 알고리즘과 달리, 방문 여부와 상관없이 매번 모든 간선을 확인해야 한다. O(VE) 소요
다익스트라 알고리즘의 최적의 해를 항상 포함하게 되지만 시간도 오래 걸린다.
다만, 음수 간선 순환을 탐지할 수 있다는 장점이 있다. 
"""

def bf(start):
    distance[start] = 0
    # n번 검사
    for i in range(n):
        # 모든 간선 확인
        for start in range(1, n+1):
            for next_node, next_cost in graph[start]:
                if distance[next_node] > distance[start] + next_cost:
                    # 다음 노드까지의 최단거리 갱신
                    distance[next_node] = distance[start] + next_cost
                    # 마지막 반복인데 이때도 갱신이 발생한다면 음의 싸이클이 존재한다는 의미임.
                    if i == n-1:
                        return "YES"
    return "NO"

tc = int(input())
for _ in range(tc):
    n, m, w = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    distance = [10001 for _ in range(n+1)]
    # 도로 정보
    for _ in range(m):
        s, e, t = map(int, input().split())
        graph[s].append((e, t))
        graph[e].append((s, t))
    # 웜홀 정보
    for _ in range(w):
        s, e, t = map(int, input().split())
        graph[s].append((e, -t)) # 시간이 줄어든다.
    print(graph)
    print(bf(1))

  bf는 벨만포드 알고리즘을 구현한 함수이다. n번의 반복에서, 각 시작점마다 다음 노드까지의 최단거리를 갱신해준다. 만약 마지막 반복(n번째)인데도 갱신이 발생한다면 "YES"를, 그렇지 않다면 "NO"를 리턴해주도록 한다.

  입력값을 받을 때에는 일반적인 그래프 입력 방식으로 받되, 문제의 설명대로 웜홀의 가중치의 경우 음수로 받아주도록 한다.