💻 백준 1238번: 파티

문제 소개 🧐

N명의 학생들이 각자 다른 마을에 살고 있다. 이들이 X번 마을에 모여 파티를 하기로 했다. 마을 사이에는 M개의 단방향 도로가 있으며, 각 도로를 지나는 데는 특정 시간이 걸린다.

모든 학생은 자신의 마을에서 X번 마을까지 갔다가 다시 자신의 마을로 돌아와야 한다. 이때, 최단 시간으로 오고 가고 싶어 한다.

N명의 학생 중, 이 왕복 과정에 가장 많은 시간이 걸리는 학생은 누구이며, 그 시간은 얼마인지 구하는 문제다.

입력 📝

  • 첫째 줄에 N(학생 수/마을 수), M(도로 수), X(파티 장소)가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000)
  • 다음 M개의 줄에 걸쳐 도로의 시작점, 끝점, 소요 시간이 주어진다.

출력 📤

  • N명의 학생 중 가장 오래 걸리는 학생의 총 소요 시간을 출력한다.

🤔 아이디어: 다익스트라의 필요성

모든 노드 쌍 간의 최단 경로를 구해야 하는 문제처럼 보일 수 있다. 만약 그랬다면 플로이드-워셜 알고리즘을 고려했을 것이다. 하지만 플로이드-워셜은 시간 복잡도가 O(N³)이므로, N이 1,000일 때 약 10억 번의 연산이 필요해 시간 초과가 날 것이 분명했다.

따라서, 특정 지점을 기준으로 하는 최단 경로 알고리즘인 다익스트라(Dijkstra) 를 사용하였다.

핵심은 두 가지 경로의 최단 시간을 구하는 것이다.

  1. 각 마을 i에서 파티 장소 X까지 가는 최단 시간
  2. 파티 장소 X에서 각 마을 i로 돌아오는 최단 시간

🔄첫 번째 접근: 각 학생마다 다익스트라 실행

가장 직관적인 방법으로 각 학생(마을)마다 다익스트라 알고리즘을 실행했다.

  1. 모든 학생 i (1부터 N까지)에 대해, dijkstra(i)를 실행하여 X까지의 최단 거리를 구한다. (i -> X)
  2. 파티 장소 X에서 dijkstra(X)를 실행하여 모든 다른 마을 i까지의 최단 거리를 구한다. (X -> i)
  3. 각 학생 i에 대해 (i -> X) + (X -> i) 시간을 계산하고, 이 중 최댓값을 찾는다.

Code

import sys
import heapq

N, M, X = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(N+1)]

for _ in range(M):
    a, b, t = map(int, sys.stdin.readline().split())
    graph[a].append((t, b))

def dijkstra(start, graph):
    global N
    q = []
    q.append((0, start))
    path = [float('inf')] * (N+1)
    path[start] = 0

    while q:
        time, node = heapq.heappop(q)

        if path[node] < time:
            continue

        for n_t, n_node in graph[node]:
            n_time = time + n_t
            if n_time < path[n_node]:
                path[n_node] = n_time
                heapq.heappush(q, (n_time, n_node))
    return path

# X에서 집으로 돌아오는 최단 경로
x_path = dijkstra(X, graph)
answer = 0
for i in range(1, N+1):
    if i == X:
        continue
    # 집에서 X로 가는 최단 경로
    cur = dijkstra(i, graph)
    answer = max(answer, cur[X] + x_path[i])

print(answer)

Result

  • 결과: 성공! 🎉

마무리 🤔

  • 위의 방법은 N명의 학생에 대해 다익스트라를 각각 실행하므로, 총 N번의 다익스트라 연산이 필요하다. 다익스트라의 시간 복잡도는 O(M log N)이므로, 총 시간 복잡도는 O(N * M log N)이 된다. N=1,000, M=10,000일 경우 비효율적일 수 있다.

시간 복잡도를 줄일 더 효율적인 방법이 있다. 바로 역방향 그래프를 활용하는 것이다.

  • X -> i (돌아오는 길): 원래 그래프에서 다익스트라를 한 번만 실행하면 X에서 모든 다른 마을 i까지의 최단 거리를 모두 구할 수 있다.
  • i -> X (가는 길): 모든 마을 i에서 X로 가는 최단 거리를 어떻게 한 번에 구할 수 있을까? 도로의 방향을 모두 뒤집은 역방향 그래프를 만들고, X에서부터 다익스트라를 실행하면 된다. 즉, 역방향 그래프에서 X로부터 i까지의 최단 거리는 원래 그래프에서 i로부터 X까지의 최단 거리와 같다.

이 방법을 사용하면 다익스트라 알고리즘을 단 두 번만 실행하면 된다.

  1. dist_from_X: 원래 그래프에서 dijkstra(X) 실행
  2. dist_to_X: 역방향 그래프에서 dijkstra(X) 실행
  3. 각 학생 i의 총 소요 시간 = dist_to_X[i] + dist_from_X[i]

이 접근법의 시간 복잡도는 O(M log N) 으로, 훨씬 효율적이다.

  • 핵심: 다익스트라 알고리즘을 두 번 사용하여 문제를 해결한다.
  • 가는 길: 역방향 그래프를 만들어 X에서 출발하는 다익스트라를 통해 모든 노드에서 X까지의 최단 거리를 구한다.
  • 오는 길: 원래 그래프에서 X에서 출발하는 다익스트라를 통해 X에서 모든 노드까지의 최단 거리를 구한다.

‘모든 정점에서 특정 한 정점까지의 최단 경로’는 그래프를 뒤집어 ‘특정 한 정점에서 모든 정점까지의 최단 경로’ 문제로 바꿀 수 있다는 교훈을 얻었다. :teacher:

⁂