[백준 파이썬] 1865 웜홀

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

1865번: 웜홀

문제



그래프 정보가 주어진다. 임의의 경로를 정해서 해당 경로를 지나 다시 처음 지점으로 왔을 때 시간이 줄어드는 경우를 체크하는 문제이다. 

 

---

아이디어

포인트는 시간이 줄어든다는 점이다. 그래프 알고리즘에서 간선이 음수일 경우에도 거리를 구할 수 있는 알고리즘에는 벨만-포드 알고리즘이 있으므로 해당 알고리즘을 사용하면 되겠다고 생각했다.

 

벨만-포드 알고리즘

• 벨만-포드 알고리즘은 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이다.
• 간선의 가중치가 음수일 경우에도 최단거리를 구할 수 있다.

최단거리를 구하는 알고리즘에는 다익스트라 알고리즘이 있지만 간선의 가중치가 음수일 경우에는 사용할 수 없기 때문에 이경우에는 적용할 수 없다.

 

벨만 포드 알고리즘의 과정은 다음과같다.

1. 최단거리 테이블을 초기화한다.

2. 아래 과정을 (정점의 개수 - 1)만큼 반복한다.

  1. 모든 간선 E개를 하나씩 확인한다.

  2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.

 

여기서 2번과정을 한번 더 수행하면 음수 간선 순환의 발생을 체크할 수 있다.

그 이유는 음수 간선 순환이 발생하면 최단 거리 테이블이 무한정 갱신되기 때문이다. 

---

풀이

해당 문제를 풀기위해 밸만-포드 알고리즘을 적용시킨다.

하지만 문제는 음수 사이클이 존재하는지만 확인하면 되기때문에 음수 사이클의 존재를 발견하면 바로 탈출하게 수정한다.

 

for _ in range(TC):
  N, M, W = map(int, input().split())
  graph = []
  for i in range(M):
    S, E, T = map(int, input().split())
    graph.append((S, E, T))
    graph.append((E, S, T))
  
  for i in range(W):
    S, E, T = map(int, input().split())
    graph.append((S, E, -T))

먼저 테스트 케이스만큼 반복한다.

문제에서 도로는 양방향 노드이며, 웜홀은 단방향 노드이므로 해당 조건에 맞게 그래프에 입력해준다.

 

def bellmanFord(start, n):
  dist = [INF for i in range(n + 1)]
  dist[start] = 0
  for i in range(n):
    for S, E, T in graph:
      if dist[E] > dist[S] + T: #최단 거리 테이블이 갱신됨
        if i == n - 1:  #음수 순환이 발견됨
          return True
        dist[E] = dist[S] + T
  
  return False

 

 

다음은 벨만포드 알고리즘이다.

1. 먼저 거리테이블을 무한으로 초기화 시킨다.

2. 그 후 그래프에 있는 정보를 이용하여 최단 거리 테이블을 갱신한다.

3. n번째의 순환에서 음수 순환이 발견되면 탈출한다.

 

 

 

 

---

코드

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

def bellmanFord(start, n):
  dist = [INF for i in range(n + 1)]
  dist[start] = 0
  for i in range(n):
    for S, E, T in graph:
      if dist[E] > dist[S] + T: #최단 거리 테이블이 갱신됨
        if i == n - 1:  #음수 순환이 발견됨
          return True
        dist[E] = dist[S] + T
  
  return False

TC = int(input())

for _ in range(TC):
  N, M, W = map(int, input().split())
  graph = []
  for i in range(M):
    S, E, T = map(int, input().split())
    graph.append((S, E, T))
    graph.append((E, S, T))
  
  for i in range(W):
    S, E, T = map(int, input().split())
    graph.append((S, E, -T))
  
  result = bellmanFord(1, N)

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