[BOJ] 백준 1238번 파티 문제 풀이 (Python)

1. 문제 풀이 방법

1.1 최단 거리 알고리즘

최단거리를 이동하는 학생들 중 가장 오래 걸리는 사람을 구하는 문제이기 때문에 최단거리 알고리즘을 이용하여 문제를 풀었다

최단거리 알고리즘은 여러가지가 존재하지만 간선의 weight가 양수라는 가정 하에 대표적으로 2가지가 존재한다.

• 다익스트라(dijkstra) 알고리즘: 특정 노드에서 다른 노드까지 최단거리를 구하는 알고리즘
  • 시간 복잡도: $O(|E|\,log(|V|)$ ($|E|$: 간선의 갯수, $|V|$: 노드의 갯수, 우선순위 큐 사용)
• 벨만-포드 알고리즘: 모든 노드에서 모든 노드까지 최단거리를 구하는 알고리즘
  • 시간 복잡도: $O(|V||E|)\approx O(|V|^3)$ ($|E|$: 간선의 갯수, $|V|$: 노드의 갯수)

주어진 노드의 갯수가 1000개이기 때문에 다익스트라 알고리즘을 사용해 문제를 풀었다.

1.2. 다익스트라 알고리즘 Tip

단방향 엣지에서 다익스트라를 이용해 문제를 풀 때 A에서 B로 가는 단일 최단 경로를 구할 때가 많아 시간 초과가 잘 발생하지 않지만 1238번과 같이 벨만-포드 알고리즘을 사용하지 못하고 모든 노드에서 특정노드로 가는 최단거리를 구해야하는 경우 시간 초과가 발생할 수 있다.

예를 들어, 노드 갯수: N, 엣지 갯수: M 라고 가정할 때 모든 노드에서 특정 노드 X로 가는 최단거리를 구한다면 시간복잡도가 대략 $O(|N-1||M|\, log(|N|)$이 된다. 다익스트라를 총 N-1번 사용해 최단 거리를 구하기 때문에 노드나 엣지 갯수가 10000보다 클 경우 시간 초과가 발생할 수 있다.

시간을 줄이는 방법은 다익스트라를 사용하는 횟수를 줄이는 것이다. 다익스트라 알고리즘을 1번만 사용해 모든 노드에서 특정 노드 X로 가는 최단 거리를 구할 수 있는데 시작점을 X로 설정하고 각 노드로 가는 최단 거리를 구하면 된다. 이 때 단방향 엣지이기 때문에 기존 엣지를 역방향으로 바꿔야한다.

의외로 간단한 방법이지만 처음 접할 때 생각을 하지 못할 수도 있다. 이 방법을 잘 기억해두어 노드나 엣지 갯수가 클 때 적용해보면 좋을 것 같다.

2. 풀이

2.1. N-1번 다익스트라를 사용해 답 구하기

모든 노드에서 X 노드로 가는 최단거리를 구할 때 다익스트라를 N-1번 사용해 문제를 푸는 방법. PyPy3 기준으로 2792ms 걸렸다.

import sys
import heapq
INF = 1e10
def input(): return sys.stdin.readline().rstrip()

def dijkstra(s):
    global x
    dist = [INF] * (n+1)
    q = []
    heapq.heappush(q,(s,0))
    while q:
        w,d = heapq.heappop(q)
        if dist[w] < d:
            continue
        for nxt,c in graph[w]:
            if dist[nxt] > d + c:
                dist[nxt] = d+c
                heapq.heappush(q,(nxt,d+c))
    if s != x:
        return dist[x]
    return dist

n,m,x = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a].append((b,c))
node2x = [0] * (n+1)
for i in range(1,n+1):
    if i != x:
        node2x[i] = dijkstra(i)
x2node = dijkstra(x)

print(max([x2node[i] + node2x[i] for i in range(1,n+1) if i != x]))

2.2. 다익스트라를 2번만 이용해 답 구하기

단방향 엣지이기 때문에 역방향 그래프를 1개 더 만들어서 특정 노드에서 X로 가는 최단거리를 구하였다. PyPy3기준으로 296ms 걸렸다.

import sys
import heapq
INF = 1e10
def input(): return sys.stdin.readline().rstrip()

def dijkstra(s, edge):
    dist = [INF] * (n+1)
    q = []
    heapq.heappush(q,(s,0))
    while q:
        w,d = heapq.heappop(q)
        if dist[w] < d:
            continue
        for nxt,c in edge[w]:
            if dist[nxt] > d + c:
                dist[nxt] = d+c
                heapq.heappush(q,(nxt,d+c))
    return dist

n,m,x = map(int,input().split())
graph = [[] for _ in range(n+1)]
reverse_graph = [[] for _ in range(n+1)]
for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a].append((b,c))
    reverse_graph[b].append((a,c))
node2x = dijkstra(x,reverse_graph)
x2node = dijkstra(x,graph)

print(max([x2node[i] + node2x[i] for i in range(1,n+1) if i != x]))