[BOJ][Python]1865 풀이

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

1865번: 웜홀

import sys
ssr = sys.stdin.readline

INF = 10001

def bellman_ford():
    min_time = [INF for _ in range(n+1)]
    min_time[1] = 0
    for i in range(1, n+1):
        for j in range(1, n+1):
            for next_node, next_time in routes[j]:
                if min_time[j]+next_time < min_time[next_node]:
                    min_time[next_node] = min_time[j]+next_time
                    if i == n:
                        return True
    return False

t = int(ssr())
for _ in range(t):
    n, m, w = map(int, ssr().split())
    routes = [[] for _ in range(n+1)]
    for _ in range(m):
        s, e, t = map(int, ssr().split())
        routes[s].append([e, t])
        routes[e].append([s, t])
    for _ in range(w):
        s, e, t = map(int, ssr().split())
        routes[s].append([e, -t])
    if bellman_ford():
        print('YES')
    else:
        print('NO')

약간 멍청한 짓을 해버렸습니다. 출력을 No라고 해놓고 왜 안되는지 계속 엄한 곳만 고치고 있었네요. 이게 제가 벨만 포드를 완전 마스터했다고 생각이 들었다면 안그랬을텐데 배우는 입장이니까 오히려 이런 부분을 틀렸을 거라고 생각을 못하네요.

 

일단 해당 문제에서 중요한 조건은 도로는 양방향이고 웜홀은 단방향, 그리고 출발점이 따로 주어지지 않는다 정도가 있겠습니다. 도로가 양방향인 부분은 사실 입력 설명에서 한 번 더 언급이 되어야 한다고 생각하는데 좋은 문제는 아니네요. 하지만 개인적으로 출발점이 따로 주어지지 않는 부분은 이 문제에서 가장 좋은 포인트가 아닌가 생각합니다.

 

해당 문제는 '출발점으로 다시 돌아올 수 있는 경우&돌아 왔을 때 처음보다 시간이 되돌아갔는지' 를 체크해서 YES, NO를 구분하여 출력하는 문제입니다. 출발 노드가 따로 주어지지 않아서 얼핏 '그럼 모든 노드에 대해서 다 벨만-포드를 적용하고 하나라도 조건에 맞으면 YES를 출력하도록 반복문을 짜야하나?'하는 생각이 들 수 있지만 출발점이 주어지지 않았다는 건 어느 위치든지 출발점으로 문제를 푸는 사람이 자유롭게 설정해도 된다는 뜻이됩니다. 그러면 우리는 해당 그래프에서 음의 사이클이 존재하는지만 확인하면 되는거죠. 음의 사이클이 존재할 때 음의 사이클에 포함되는 노드를 출발점으로 정하면 자연스럽게 출발점으로 다시 돌아오면서 시간도 되돌아가는 경우를 만족하니까요.

 

상당히 스마트한 방법으로 벨만-포드를 사용하라는 힌트를 주고있는 셈입니다. 물론 입력만 봐도 벨만 포드네 하고 알 수 있지만 약간 출제자가 머리를 쓴 것 같은 포인트가 보이니 기쁘지 않을수가 없네요. 그렇다 하더라도 굳이 별 내용 아닌 것 처럼 괄호를 쳐서 도로는 양방향이란 정보를 의도적으로 눈에 띄지 않게 한 것은 좋지 않은 방법이라고 생각합니다. 이런 포인트는 나중에 시간을 여유롭게 가지고 문제를 풀이하는 사람한테나 좋은 거지 대회에서 시간의 압박을 받으면서 푸는 사람한테 예의가 아니라고 생각하거든요.