[백준] 1865번 웜홀(python)

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

1865번: 웜홀

 

1. 난이도 골드3 (🥇)

 

2. 문제해결 과정

인터넷에 있는 많은 글들이 dist[v] != INF을 검사하지 않으면 정답 처리 된다고 했다.

그러나 벨만포드에 대한 이해도가 부족한 나는 그 말이 도무지 😭이해 되지않아 백준 질문게시판 + 이 문제와 관련된 모든 글들을 정독했다.

 

문제 해결에 가장 큰 힌트가 된 글을 jh05013님이 백준 질문게시판에 올려주신 "풀이 및 논란 완전히 정리합니다" 글이다.

참고링크 : https://www.acmicpc.net/board/view/72995

 

솔직히 내가 이해한 게 틀릴 수도 있고(주의주의), 이 글을 참고하신 다른 분들의 풀이가 이 글의 논리와 맞는지 의문을 가지고 있다.

 

 

 

우선 이 문제에서 간과할 수 있는 점은 "백준이의 시작점은 정해지지 않았다." 이다. 즉, 한 정점을 정하고 문제를 풀면 단절된 음의 사이클을 알아낼 수 없다는 것이다.

 

이제 두 가지의 경우로 나눠서 논리를 살펴보자.

 

 

 

첫 번째, dist[v] != INF를 지운 풀이

 

우선 dist가 INF인 경우는 "시작 정점과 단절이 되어 방문하지 않는다"를 의미한다.

 

그렇기 때문에 dist[V] != INF 라는 문구를 지우고 음의 사이클의 여부를 확인했다는 것은 V를 방문하지 않았다가 아닌  V를 이미 방문을 했고,  V까지의 거리가 INF이다. 로 인식된다.

 

논리적으로 모든 정점이 연결되어있다고 처리되어 음수사이클이 있으면 YES 로 출력하는 것이다.

 

어쨌든 정답은 맞으나? 정점이 실제로 도달 가능한 건지 알 수 없게 만들고 결과적으로 올바른 벨만포드 알고리즘이라고 할 수 없다는 것 같다.

 

 

 

두 번째, 기존의 벨만포드 방식으로 구현한 풀이

 

이 경우에는 시작점과 연결되어 있지 않은 곳에 위치한 음수사이클을 찾을 수 없다.

 

문제에서 주어진 조건은 '나라 전체 중 어딘가에 있는 음수사이클의 여부'라서 오류가 발생한다.

 

 

 

jh05013님의 글을 참고하자면 이 문제의 해결 방법은 두 가지가 있다.

 

1. 모든 정점을 동시에 시작

2. N+1 번째의 가짜 정점을 만들기

 

 

1번 풀이는 dist를 INF가 아닌 0으로 설정하고 벨만포드 알고리즘을 돌리면 된다고 하셨지만 도저히 과정이 이해가 안되어서 2번 풀이만 시도해봤다.

 

 

2번 풀이는 n+1의 가짜 정점이 모든 정점과 연결되어있다는 가정을 갖고 음의 사이클의 여부를 확인하는 것이다.

 

for _ in range(t):  
  n,m,w = map(int,input().split()) #n지점 m도로 w웜홀
  x = n+1
  edges = [(x,i,0) for i in range(1,n+1)]
  dist = [INF] * (n+2)

 

N+1 번째의 가짜 정점을 만들기 위해 dist 의 크기를 하나 늘려준다. 또한 edges 리스트에 (n+1번 정점 -> 1번 정점), (n+1번 정점과 2번 정점),,, 이렇게 모든 정점과 이어질 수 있는 가상의 도로를 추가한다.

 

(거리에 영향을 주지 않기 위해 가중치는 0으로 두었다.)

 

  for _ in range(m): #도로
    s,e,t = map(int,input().split()) #s출발 e도착 t가중치
    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))

 

문제에서 제시한 조건을 보면 도로는 무방향, 웜홀은 양방향이다.

 

edges에 삽입을 할 때 위의 코드처럼 넣어주었다.

 

  cycle = bf(n+1)

 

벨만포드 알고리즘의 시작점을 n+1 (처음에 잡은 가짜 정점) 으로 잡고 벨만포드 알고리즘을 돌린다.

 

def bf(start):
  
  dist[start] = 0

  for i in range(n+1):
    for j in range(len(edges)):
      cur = edges[j][0]
      next_node = edges[j][1]
      cost = edges[j][2]

      if dist[cur] != INF and dist[next_node] > cost + dist[cur]:
        dist[next_node] = cost + dist[cur]
        if i == (x-1):
          return True
  return False

 

정점이 하나 늘었다고 생각하고 벨만포드 알고리즘을 실행시킨다.

 

이렇게 되면 'n+1정점'과 n개의 정점 사이의 최단경로가 dist 리스트에 들어가서 벨만포드의 개념을 위배하지 않고 음의사이클을 확인할 수 있게 된다.

 

+ 간선이 m개가 아니기 때문에 len(edges)만큼 반복하며 최단거리를 갱신해준다.)

 

+ if == (x-1): 에서 x는 n+1 이다.

 

 

3. 전체코드

INF = int(1e9)

t = int(input()) #테스트케이스

def bf(start):
  
  dist[start] = 0

  for i in range(n+1):
    for j in range(len(edges)):
      cur = edges[j][0]
      next_node = edges[j][1]
      cost = edges[j][2]

      if dist[cur] != INF and dist[next_node] > cost + dist[cur]:
        dist[next_node] = cost + dist[cur]
        if i == (x-1):
          return True
  return False


for _ in range(t):
  
  n,m,w = map(int,input().split()) #n지점 m도로 w웜홀

  x = n+1

  edges = [(x,i,0) for i in range(1,n+1)]

  dist = [INF] * (n+2)

  for _ in range(m): #도로
    s,e,t = map(int,input().split()) #s출발 e도착 t가중치
    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))

  cycle = bf(n+1)

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

 

4. dist[v] != INF를 지운 일반적인 코드

INF = int(1e9)

t = int(input()) #테스트케이스

def bf():

  for i in range(n):
    for j in range(len(edges)):
      cur = edges[j][0]
      next_node = edges[j][1]
      cost = edges[j][2]

      if dist[next_node] > cost + dist[cur]:
        dist[next_node] = cost + dist[cur]
        if i == n-1:
          return True

  return False


for _ in range(t):

  edges = []
  
  n,m,w = map(int,input().split()) #n지점 m도로 w웜홀

  dist = [INF] * (n+1)

  for _ in range(m): #도로
    s,e,t = map(int,input().split()) #s출발 e도착 t가중치
    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))

  cycle = bf()

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

 

 

 

이해가 안돼서 무시무시하게 많이 틀리고, 시간도 오래 걸렸지만

 

벨만포드 알고리즘에 대한 이해도를 많이 높일 수 있었던 좋은 문제였다!