[백준] 1865번: 웜홀 - 파이썬

🔈 문제

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

 

📝입력

첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), 도로의 개수 M(1 ≤ M ≤ 2500), 웜홀의 개수 W(1 ≤ W ≤ 200)이 주어진다. 그리고 두 번째 줄부터 M+1번째 줄에 도로의 정보가 주어지는데 각 도로의 정보는 S, E, T 세 정수로 주어진다. S와 E는 연결된 지점의 번호, T는 이 도로를 통해 이동하는데 걸리는 시간을 의미한다. 그리고 M+2번째 줄부터 M+W+1번째 줄까지 웜홀의 정보가 S, E, T 세 정수로 주어지는데 S는 시작 지점, E는 도착 지점, T는 줄어드는 시간을 의미한다. T는 10,000보다 작거나 같은 자연수 또는 0이다.
두 지점을 연결하는 도로가 한 개보다 많을 수도 있다. 지점의 번호는 1부터 N까지 자연수로 중복 없이 매겨져 있다.

 

📑출력

TC개의 줄에 걸쳐서 만약에 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능하면 YES, 불가능하면 NO를 출력한다.

 

📚 문제 풀이

이 문제를 보고 처음에는 웜홀은 제외하고 데이크스트라 알고리즘을 사용해서 각각의 최단거리를 알아낸 다음 웜홀의 마이너스 값을 연산하여 음수가 나오는 거리가 있다면 'YES'를 출력하면 되겠다고 생각했다.

그렇게 i노드에서 출발했을때 다른 노드의 최단거리를 알아냈는데 다시 돌아오는 거리를 계산하려면 또 다른 구현을 해야했다...ㅋㅋㅎ

노드가 총 3개 있을 때 1번 노드에서 출발하면 결과값은 예를 들어 [0, 3, 1] 이런식으로 출발 노드는 0으로 결과값이 나오기 때문에 한바퀴 돌아왔을 때 거리를 알수가 없었다.

 

밑에 알고리즘 분류를 보았는데 벨만 포드 알고리즘이라고 적혀있었다. 그래서 처음에는 벨만 포드 알고리즘은 바로 한바퀴 돌아오는 값을 구할 수 있을까하고 구글링해본 결과 그건 아니었다..ㅎ

 

데이크스트라 알고리즘과 벨만 포드의 차이점은 바로 음수의 간선에 있었다.

데이크스트라 알고리즘은 음수의 간선을 인지 못하고 그냥 지나쳐 버린다. 그리디하게 작동하기 때문에 뒤에 있는 음수의 간선은 파악하지 못하고 지나쳐 버린다는 것이다. 이에 반면 벨만 포드 알고리즘은 이웃한 노드를 전부 방문하기 때문에 음수의 간선의 존재를 알 수 있다.

 

도로와 웜홀을 딕셔너리에 한번에 담는다. 노드를 잇는 도로나 웜홀은 하나 이상이 존재할 수도 있기 때문에 가장 작은 값만 존재하도록 처리했다.

요거 잘 처리하고 벨만 포드 알고리즘 돌리니 정답 판정을 받았다.

 

💻 코드

import sys
input = sys.stdin.readline

# 벨만 포드 알고리즘 구현
def bellman_ford(graph, start):
    distance= dict()
    for node in graph:
        distance[node] = 5000 * 10000 # 무한 값으로 초기화
    distance[start] = 0

    for i in range(len(graph)-1):
        for node in graph:
            for neighbor in graph[node]:
                if distance[neighbor] > distance[node] + graph[node][neighbor]:
                    distance[neighbor] = distance[node] + graph[node][neighbor]
    
    for node in graph:
        for neighbor in graph[node]:
        	# 한번 더 돌았을 때도 이게 가능하다면 시간 줄음
            if distance[neighbor] > distance[node] + graph[node][neighbor]:
                return 'YES'
    
    return 'NO'


for _ in range(int(input())):
    n,m,w = map(int,input().split())
    graph = dict()
    # 틀만들기
    for i in range(1, n+1):
        graph[i] = {}

    for j in range(m):
        s,e,t=map(int,input().split())
        # 이전에 이미 도로가 있다면
        if e in graph[s]:
        # 최소값으로 업데이트
            graph[s][e] = min(graph[s][e], t)
        else:
            graph[s][e] = t

        if s in graph[e]:
            graph[e][s] = min(graph[e][s], t)
        else:
            graph[e][s] = t

    for k in range(w):
    # 웜홀
        s,e,t = map(int,input().split())
        graph[s][e] = -t

    print(bellman_ford(graph, 1))

 

🍭 시행착오

틀린 이유는 무한 값을 너무 작게 잡았기 때문이다. 시간 초과가 난 이유는 모든 노드에서 값을 체크했기 때문이다. 해당 문제(Not Problem)는 출발 노드를 따로 지정해주지 않았는데 소스코드에는 1번 노드만 탐색을하고 바로 답을 유추하였다. 왜냐 전부 연결되어 있는 그래프이기 때문인거 같긴한데 정확하게 증명하지는 못하겠다. 아직 벨만 포드 알고리즘을 완벽하게 이해하지는 못하겠으나 작동원리는 감이 온거 같다.

🔗 문제링크 웜홀

1865번: 웜홀