[백준1865&파이썬] 플로이드 와샬을 통해 음의 사이클 판단하기

# 문제

백준 1865 웜홀 파이썬 풀이

1865번: 웜홀

# 코드

import sys
from collections import defaultdict

def print2D(arr) :
  for i in arr :
    print(i)
  print()

TC = int(sys.stdin.readline().strip())

def solve() :
  # N 지점의 개수, M 도로의 개수, W 월홀의 개수
  N,M,W = map(int,sys.stdin.readline().split())

  # 플로이드-와샬을 통해서 음의 사이클이 형성되면 종료 후 "YES" 출력하면 됨
  distance = [ [10_001] * (N + 1) for _ in range(N + 1)]

  # 초기화 수행
  for i in range(N+1) :
    distance[i][i] = 0

  # 도로의 정보, 양방향 그래프
  for _ in range(M) :
    S,E,T = map(int,sys.stdin.readline().split())
    if T < distance[S][E] :
      distance[S][E] = T

    if T < distance[E][S] :
      distance[E][S] = T

  # 웜홀의 정보, 단방향 그래프
  for _ in range(W) :
    S, E, T = map(int, sys.stdin.readline().split())
    if -T < distance[S][E] :
      distance[S][E] = -T



  for pivot in range(1,N+1) :
    for start in range(1,N+1) :
      for end in range(1,N+1) :
        cost = distance[start][pivot] + distance[pivot][end]
        if cost < distance[start][end]:
          distance[start][end] = cost
          if start == end and cost < 0 :
            print("YES")
            # print2D(distance)
            return
  # print2D(distance)
  print("NO")

for _ in range(TC) :
  solve()

# 풀이

• 시작점에서 한바퀴 돌아서 다시 시작점으로 도착했을 경우 음의 가중치를 가지는지 판단하는 문제이다.
• 문제를 분해해보다 보니 결국 음의 사이클을 가지는지 판단하는 문제였다.
• 플로이드 와샬을 통해서 한정점에서 모든정점까지의 최단거리를 구하고, 구하는 도중 start == end가 음이 되는 갱신이 이루어지는 순간 반환하는 로직이다.
• 자기 자신을 0으로 수행하는 코드 후에도 cost가 음이 된다면 가중치가 갱신되니, 플로이드 와샬을 이용하는 풀이가 사용이 가능했다.
• 다만 음의 사이클을 판단하는 문제는 벨만-포드로 많이 푸는거 같았다.
• 가중치의 저장은 항상 최솟값만을 저장시키도록 한다면, 시간도 줄일 수 있기 때문에 그렇게 수행했다.

  # 초기화 수행
  for i in range(N+1) :
    distance[i][i] = 0

• 위 코드를 가중치 입력을 다 받고 수행했었는데, 그렇게 하니까 웜홀이 distance[p][p] = -3으로 들어오는 경우를 감지하지 못했다.