[Baekjoon 1238] 파티

문제

💛Ⅲ [Baekjoon 1238 - 파티]

문제 풀이 방법

N명의 학생들의 마을로부터 X까지의 가는 최단거리와 X로부터 N명의 학생들의 마을까지의 최단거리를 각각 구해야 한다. X로부터 N명의 학생들의 마을까지는 다익스트라 알고리즘을 그대로 사용하여 구할 수 있다. 하지만 N명의 학생들의 마을로부터 X까지의 최단거리를 어떻게 구해야 할지가 어려웠다.

1. 그냥 플로이드-워셜 알고리즘을 사용하여 모든 마을 사이의 최단거리를 구한다. → 시간복잡도 $O(V^3)$이다.
2. 다익스트라를 N만큼 반복하여 각 마을마다 최단거리를 구한다. → 시간복잡도 $O(V*ElogV)$이다.

두 방법 모두 시간복잡도 측면에서 좋지 않다고 생각하였고, 질문하기 게시판에서 다익스트라 알고리즘을 2번만 사용하여 구해야 한다는 글을 보았고, 오랜 고민 끝에 어떻게 2번만 사용하여 구하는지를 이해 하였다!!

1. X로부터 각 마을까지의 경로는 go_graph라는 리스트에 저장한다.
2. 각 마을로부터 X까지의 경로는 back_graph라는 리스트에 거꾸로 저장한다.
   → 이 상태에서 X로 시작하는 다익스트라 알고리즘을 수행하면?
   예를 들어 2번 마을까지의 최단 경로는 X → 1 → 3 → 2 와 같이 나올 수 있다. 이 때, 거꾸로 저장했기 때문에 실제 경로가 의미하는 것은 2 → 3 → 1 → X가 되는 것이다! 즉, 경로를 거꾸로 저장하고 다익스트라를 한 번 수행하면 각 마을로부터 X까지의 최단거리를 한 번에 구할 수 있다!!

풀이 코드

Python

def dijkstra(start, distance, graph):
    q = []
    heapq.heappush(q,(0,start))
    distance[start] = 0
    while q:
        dist, node = heapq.heappop(q)
        if distance[node] < dist: # 이미 처리한 적 있는 노드라면 무시
            continue
        for i in graph[node]: # 현재 노드와 연결된 노드들 확인
            cost = dist+i[1] # 거리 계산
            if cost < distance[i[0]]: # 현재 최단거리보다 작다면 갱신하고 힙에 push
                distance[i[0]] = cost
                heapq.heappush(q,(cost, i[0]))

# 다익스트라 알고리즘
import sys, heapq
sys = sys.stdin.readline

INF = int(1e9)
N,M,X = map(int, input().split())

go_graph = [[] for _ in range(N+1)]
back_graph = [[] for _ in range(N+1)]
go_distance = [INF] * (N+1)
back_distance = [INF] * (N+1)

for _ in range(M):
    a,b,c = map(int, input().split())
    go_graph[a].append((b,c))
    back_graph[b].append((a,c))

dijkstra(X,go_distance, go_graph)
dijkstra(X,back_distance, back_graph)

print(max([x+y for x,y in zip(go_distance[1:], back_distance[1:])]))