💻 백준 1865번: 웜홀

문제 소개 🧐

N개의 지점, M개의 도로, W개의 웜홀이 있다. 도로는 양방향이며 이동 시 시간이 걸리지만, 웜홀은 단방향이며 통과 시 시간이 거꾸로 간다.

한 지점에서 출발하여 다시 출발 위치로 돌아왔을 때, 시간이 출발 시점보다 이전으로 돌아가는 경우(음수 사이클)가 존재하는지 판별하는 문제다.

입력 📝

  • 첫째 줄: 테스트케이스 수 TC
  • 각 테스트케이스 첫째 줄: 지점 수 N, 도로 수 M, 웜홀 수 W
  • 도로 정보(M개): S, E, T (S-E 연결, 시간 T 소요)
  • 웜홀 정보(W개): S, E, T (S->E 이동, 시간 T 감소)

출력 📤

  • 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능하면 YES, 불가능하면 NO를 출력한다.

나의 풀이 ✨

음수 가중치를 포함한 그래프에서 음수 사이클의 존재 여부를 찾는 전형적인 문제다. 이 문제를 해결하기 위해 여러 최단 경로 알고리즘을 시도했다.

Idea 1: 플로이드-워셜

모든 지점 쌍 간의 최단 경로를 구하는 플로이드-워셜 알고리즘을 사용해보기로 했다. 알고리즘을 실행한 후, path[i][i] (i에서 시작해 i로 돌아오는 경로)의 값이 음수이면 음수 사이클이 존재한다고 판단할 수 있다.

Code
import sys

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

def floyd_warshall(graph, n):
    path = [row[:] for row in graph]
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                path[i][j] = min(path[i][j], path[i][k] + path[k][j])
    return path

for _ in range(TC):
    n, m, w = map(int, sys.stdin.readline().split())
    graph = [[float('inf')]*(n+1) for _ in range(n+1)]
    for _ in range(m):
        s, e, t = map(int, sys.stdin.readline().split())
        graph[s][e] = min(graph[s][e], t)
        graph[e][s] = min(graph[e][s], t)
    
    for _ in range(w):
        s, e, t = map(int, sys.stdin.readline().split())
        graph[s][e] = min(graph[s][e], -1*t)

    for i in range(1,n+1):
        graph[i][i] = 0
    
    shortest_paths = floyd_warshall(graph, n)

    is_time_travel = False
    for i in range(1, n+1):
        if shortest_paths[i][i] < 0:
            is_time_travel = True
            break
    
    print("YES") if is_time_travel else print("NO")
Result: 시간 초과

플로이드-워셜의 시간 복잡도는 O(N³)이다. N이 최대 500이므로, 500³은 약 1억 2500만으로 시간 제한(2초)을 초과할 수밖에 없었다. 음수 사이클 판별에 더 효율적인 알고리즘이 필요했다.

Idea 2: 벨만-포드 (모든 노드에서 시작)

음수 가중치 그래프에서 사용 가능한 벨만-포드 알고리즘(O(VE))을 사용하기로 했다. 벨만-포드는 V-1번의 완화(relaxation) 후, V번째 완화에서 또 거리가 갱신되면 음수 사이클이 존재한다고 판단한다.

그래프가 여러 컴포넌트로 나뉘어 있을 수 있으므로, 모든 노드를 시작점으로 하여 벨만-포드를 실행했다.

Code
import sys

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

def bellmanFord(graph_edges, n, start):
    dist = [float('inf')] * (n+1)
    dist[start] = 0

    for i in range(1, n):
        for u, v, w in graph_edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    for u, v, w in graph_edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return dist, True
    
    return dist, False

for _ in range(TC):
    n, m, w = map(int, sys.stdin.readline().split())
    edge_list = []
    # ... (이전과 동일)
    
    has_cycle = False
    for i in range(1, n+1):
        shortest_paths, has_cycle = bellmanFord(edge_list, n, i)
        if has_cycle:
            break
    
    print("YES") if has_cycle else print("NO")
Result: 67% 시간 초과

모든 노드(N개)에 대해 벨만-포드(O(VE))를 실행하니 시간 복잡도는 O(N*VE)가 되어 여전히 시간 초과가 발생했다. 한 번의 벨만-포드 실행으로 전체 그래프의 음수 사이클을 감지할 방법이 필요했다.

Idea 3: 벨만-포드 + 가상 시작점

모든 노드와 연결된 가상의 시작 노드(0번)를 만들고, 이 노드에서 각 실제 노드(1~N)로 가는 가중치 0의 간선을 추가했다. 이렇게 하면 그래프가 여러 컴포넌트로 나뉘어 있더라도, 가상 노드에서 출발하는 한 번의 벨만-포드 실행만으로 모든 노드를 방문하고 전체 그래프의 음수 사이클 존재 여부를 판별할 수 있다.

Code
import sys

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

def bellmanFord(graph_edges, n, start):
    dist = [float('inf')] * (n+1)
    dist[start] = 0

    for _ in range(0, n):
        for u, v, w in graph_edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    for u, v, w in graph_edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return dist, True
    
    return dist, False

for _ in range(TC):
    n, m, w = map(int, sys.stdin.readline().split())
    edge_list = []
    # ... (이전과 동일)
    
    # 가상의 노드 추가
    for i in range(1, n+1):
        edge_list.append((0, i, 0))
    
    shortest_paths, has_cycle = bellmanFord(edge_list, n, 0)
    
    print("YES") if has_cycle else print("NO")
Result: 성공! 🎉

이 방법은 O(VE)의 시간 복잡도로 문제를 해결할 수 있었다.

마무리 🤔

  • 알고리즘 선택의 중요성: 문제의 제약 조건(N, M, W의 크기)을 보고 O(N³)인 플로이드-워셜이 아닌 O(VE)인 벨만-포드를 선택해야 했다.
  • 연결되지 않은 그래프 처리: 그래프가 여러 컴포넌트로 나뉘어 있을 경우, 모든 컴포넌트를 탐색하기 위해 가상의 시작 노드를 추가하는 트릭은 매우 유용하다.
  • 벨만-포드의 원리: V-1번의 완화로 모든 최단 경로를 찾고, V번째 완화에서 갱신이 일어난다면 음수 사이클이 존재한다는 벨만-포드의 핵심 원리를 정확히 이해하고 적용하는 것이 중요했다.

시간 초과를 통해 더 효율적인 알고리즘을 고민하고, 문제 상황에 맞게 알고리즘을 변형(가상 노드 추가)하는 좋은 경험이었다.

⁂