[백준 1238 🥇] 파티

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

문제풀이

import sys
import heapq


n,m,x=map(int, sys.stdin.readline().split(' '))
path=[[] for _ in range(n+1)]
# 역방향그래프
pathR=[[] for _ in range(n+1)]
for _ in range(m):
    s,e,t=map(int, sys.stdin.readline().split(' '))
    path[s].append((e,t))
    pathR[e].append((s,t))

# party에서 각 마을로 돌아가는 최단 경로
fromParty=[1e9]*(n+1)
fromParty[x]=0

heap=[]
heapq.heappush(heap, (0,x))
while heap:
    time, cur = heapq.heappop(heap)
    # 이미 처리되어 있는 지점이라면 즉, 이전에 계산된 최단 경로가 현재 이 time 값보다 작아서 현재 time을 가지고 더 이상 계산해 줄 필요가 없음
    if time > fromParty[cur]:
        continue
    for nn,nt in path[cur]:
        if fromParty[nn]>time+nt:
            fromParty[nn]=time+nt
            heapq.heappush(heap, (time+nt, nn))

# 각 마을에서 party로 가는 최단 경로
toParty=[1e9]*(n+1)
toParty[x]=0
heapR=[]
heapq.heappush(heapR, (0,x))
while heapR:
    time, cur = heapq.heappop(heapR)
    # 이미 처리되어 있는 지점이라면 즉, 이전에 계산된 최단 경로가 현재 이 time 값보다 작아서 현재 time을 가지고 더 이상 계산해 줄 필요가 없음
    if time > toParty[cur]:
        continue
    for nn,nt in pathR[cur]:
        if toParty[nn]>time+nt:
            toParty[nn]=time+nt
            heapq.heappush(heapR, (time+nt, nn))

ans=-1e9
for i in range(1,n+1):
    ans=max(ans, toParty[i]+fromParty[i])

print(ans)

• 각 n번째 마을에서 x번째 마을로 가는 최단 경로를 구하고 배열에 저장한다. (toParty)
• x번째 마을에서 각 n번째 마을로 가는 최단 경로를 구하고 배열에 저장한다. (fromParty)
• 마지막으로 각 마을의 위치별로 두 배열의 값을 더한 값 중 가장 큰 값을 출력하면 된다.
• 먼저, x번째 마을에서 n번째 마을로 가는 최단 경로가 저장된 fromParty를 구하는 방식은 전형적인 다익스트라 알고리즘을 사용한다.
• 다익스트라 알고리즘을 설명하자면 다음과 같다.
  • 출발 노드에서 각 노드별로 갈 수 있는 최단 경로를 저장할 배열을 1e9 값으로 초기화해서 선언한다.
  • 이 배열에 출발 노드에 해당하는 값은 0으로 초기화하고, (0, 출발 노드)를 heap에 넣어준다.
  • 이제 heap을 pop하면서 pop한 노드에 연결된 노드와 가중치들을 탐색한다. (heap을 사용했기 때문에 저장된 값 중 가중치가 가장 작은 값이 우선적으로 pop된다.)
  • 탐색 과정에서 현재 최단 경로로 저장된 값보다 pop한 가중치 + 현재 노드와 연결된 노드와의 가중치 값이 더 작다면 현재 최단 경로를 업데이트한다.
  • 이 과정을 heap에 존재하는 값이 없을 때까지 반복하면 출발 노드에서 각 노드로 향하는 최단 경로를 구할 수 있다. 
• 여기서 x번째 마을에서 각 n번째 마을로 가는 최단 경로인 fromParty를 구할 때는 입력받은 기존의 경로를 사용하면 된다.
  • 예제를 예로 들면, 2->1, 2->3, 2->4로 가는 최단 경로를 구하는 것이다.
• 하지만, 각 n번째 마을에서 x번째 마을로 가는 최단 경로인 toParty는 입력받은 기존의 경로를 역방향으로 저장해서 구해야 한다.
  • 예제를 예로 들면, 1->2, 3->2, 4->2로 가는 최단 경로를 구해야 하는데, 이것은 각 노드마다 다익스트라를 실행해야 하므로 시간복잡도가 커질 수 밖에 없다. 
  • 그래서 기존의 경로를 역방향으로 저장해서 다익스트라를 한 번만 실행해서 2->1, 2->3, 2->4를 구한다.
    • 기존의 경로로 한 1->2, 3->2, 4->2 값과 동일한 값을 가지게 된다.