[BOJ] 1238. 파티(🥇, 다익스트라)

🔗 문제 링크

풀이

🥲 일반 다익스트라(1288ms)

N번 마을 → X번 마을 → N번 마을 로 올 수 있는 최단 경로를 찾으면 된다. M개의 경로를 통해 각 마을에서 다른 마을들로 갈 수 있는 최단 경로를 모두 구한 다음에 (1) N → X (2) X → N 이 두 가지 경로를 더한 값의 최대값을 구하면 된다.

범위가 크지 않다면 플로이드 워셜 알고리즘으로 해결할 수 있겠지만 이 알고리즘은 시간 복잡도가 O(n^3)이고 N의 최대값은 1000이므로 불가능하다.

대신 각각의 N에 대해서 힙 자료구조를 사용한 다익스트라 방식을 사용하면 되는데 이때 N마을들에서는 X마을까지의 위치만 구하면 되고, 모든 마을까지의 거리를 구해야 하는 건 X마을만 하면 된다. 일단 이 부분의 예외 처리는 하지 않은 상태에서 아래와 같이 모든 N마을에 대한 다른 마을들의 최단 거리를 구했다.

실수한 점

이때 time을 처음부터 2차원 배열로 선언하고 가져다 쓰는 방식을 택했는데, 생각해보니 어차피 다익스트라는 n마을에서 다른 마을로의 최단거리를 가지는 1차원 배열을 반환하게 되어있기 때문에 각 마을에 대한 최단거리 값들을 구한 다음에 return 해서 time 배열에 추가해주면 됐다.

힙에서 다음 최단 경로를 구하기 위한 위치값을 꺼낼 때, 방문처리 댓니 사용하게 되는 res[i] != t에서도 continue를 사용해서 이번 회차만 넘어가도록 했어야 하는데 return을 사용해서 계속 에러를 냈다.

import heapq

def dijk(s, x): # s: 시작하게 되는 지점
    res = [1e9]*n
    res[s] = 0
    pq = [(0, s)]
    while pq: 
        t, i = heapq.heappop(pq)
        if res[i] != t:
            continue
        for j, jt in arr[i]:
            dist = t + jt
            if res[j] > dist:
                res[j] = dist
                heapq.heappush(pq, (dist, j))

    return res

n, m, x = map(int, input().split())
x -= 1
arr = [[]*n for _ in range(n)]

for _ in range(m):
    a, b, t = map(int, input().split())
    arr[a-1].append((b-1, t))

time = []
for i in range(n):
    time.append(dijk(i, x))

mv = 0
for i in range(n):
    mv = max(mv, time[i][x]+time[x][i])
print(mv)

😇 역방향 다익스트라(300ms)

각각의 N마을에서는 X마을까지의 거리만 구하면 된다

이 점을 생각해보면 N마을에서 X마을까지 가는 단방향 거리들을 거꾸로 설정(역방향)한 다음에 X마을로부터 다른 마을들까지의 최단 거리를 구하면 그게 N마을에서 X마을까지의 최단거리가 되지 않을까?

X = 1일 때 아래와 같은 상황이라면, 이 방향을 거꾸로 해주면 1에서 다른 마을들로 가는 최단 거리 = 다른 마을에서 1로 오는 최단거리가 될 수 있는 것이다. 사실 우리는 2번에서 1번으로 가는 최단 거리만 알면 되는데 위의 풀이에서는 2번에서 3번, 4번, 5번으로 가는 모든 최단거리를 어쩔 수 없이 다 구해야 한다.

import heapq
import sys
input = sys.stdin.readline

def dijk(arr, s): # s: 시작하게 되는 지점
    res = [1e9]*n
    res[s] = 0
    pq = [(0, s)]
    while pq: 
        t, i = heapq.heappop(pq)

        if res[i] != t:
            continue

        for j, jt in arr[i]:
            dist = t + jt
            if res[j] > dist:
                res[j] = dist
                heapq.heappush(pq, (dist, j))
    return res

n, m, x = map(int, input().strip().split())
x -= 1
graph = [[]*n for _ in range(n)]
reverse = [[]*n for _ in range(n)]

for _ in range(m):
    a, b, t = map(int, input().strip().split())
    graph[a-1].append((b-1, t))
    reverse[b-1].append((a-1, t))

graph_dist = dijk(graph, x) # x로부터 다른 곳까지의 거리
reverse_dist = dijk(reverse, x) # 다른 곳으로부터 x까지의 거리

print(max([graph_dist[i] + reverse_dist[i] for i in range(n)]))