[백준BOJ] 1865번 웜홀.py

 

백준 저지에서 웜홀을 파이썬을 통해 풀어 보았다. 

 

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

1865번: 웜홀

1865번 웜홀.py

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

 

1865번 웜홀

문제

때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.
시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

설명

결론부터 말하자면 벨만 포드 알고리즘을 응용하여 푸는 문제이다. 처음에 최단 경로만 보고 다익스트라로 풀었다가 틀리고 그 다음엔 DFS로 풀었다가 틀려서 구글링을 통해 벨만 포드 알고리즘이 있다는 것을 찾았다.

 

벨만 포드 알고리즘이란 다익스트라 알고리즘과 마찬가지로 최단 경로를 찾는 알고리즘이다. 단 다익스트라와는 다르게 간선이 음수일 때도 사용가능하다. 추가로 다익스트라보다 빅오가 느리기 때문에 상황에 알맞게 사용해야 한다.

 

벨만 포드 알고리즘에서 최단 경로를 찾기 위한 두 가지 특징이 있다. 다익스트라와 달리 벨만포드는 정점의 개수가 N일 때 N-1번만큼만 반복한다. 최단 경로라면 무조건 N-1개의 간선만을 타기 때문이다. 단 그래프가 음수 사이클을 가진다면 최단 경로를 구할 수 없다. 벨만 포드 알고리즘은 이전 노드로부터 다음 노드로 가는 간선을 더 했을 때 기존 경로보다 작다면 갱신시키는 방식인데 음수 사이클을 가진다면 갱신된 곳이 무한으로 갱신되기 때문에 사이클을 빠져나가지 못한다. 

 

이 문제에서는 최단 경로를 찾는 것이 아닌 출발지점으로 돌아왔을 때 음의 값을 가지는지 묻고 있다. 그래프가 음의 사이클을 가지고 있다면 출발지점으로 돌아왔을 때 무조건 음의 값을 가질 수 있다. 즉 벨만 포드 알고리즘을 통해 음의 사이클을 가지는 지 확인하면 어떤 점에서 출발하던지 다시 출발지점으로 왔을 때 음수를 가지는게 가능하다.

 

처음에는 위 사실을 인지하지 못하고 모든 점에서 벨만 포드를 돌려봤는데 벨마 포드 알고리즘을 N만큼 수행하다보니 90%에서 시간 초과가 나왔다. 위 사실을 인지하고 벨만 포드를 한 번만 돌려서 맞출 수 있었다.

코드

#1865번 웜홀.py
from collections import deque
import sys
input = sys.stdin.readline

#벨만 포드 알고리즘을 응용한 문제
def bellman_ford(start) : 
    N = len(graph)
    time = [int(1e9)]*N
    time[start]=0

    for i in range(N-2) :
        for node in range(1,N) : 
            for next in graph[node] : 
                if time[next[0]] > time[node] + next[1] : 
                    time[next[0]] = time[node] + next[1] 
    
    for node in range(1,N) : #음의 사이클이 있으면 "출발점으로 돌아왔을 때 시간이 되돌아가 있는 경우 가능"
            for next in graph[node] : 
                if time[next[0]] > time[node] + next[1] : #음의 사이클
                    return True 
    
    return False 
    
TC = int(input())
for t in range(TC):
    N,M,W = map(int,input().split())
    graph = [[]for _ in range(N+1)]
    
    for m in range(M):
        S,E,T = map(int,input().split())
        graph[S].append([E,T])
        graph[E].append([S,T])
    for w in range(W):
        S,E,T = map(int,input().split())
        graph[S].append([E,-1*T])

    check=False
    if bellman_ford(1) :
         check = True
    if check : 
        print("YES")
    else : 
        print("NO")