[백준 1238번] 파티

https://www.acmicpc.net/problem/1238

import sys
import heapq

input = sys.stdin.readline

# N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.
# 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비

# N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다

n, m, x = map(int,input().split())

INF = float("inf")

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

total_length = [0]*(n+1)

for _ in range(m):
    start, end, t = map(int,input().split())
    graph[start].append((end,t))

def dijkstra(start): # 출발 노드를 설정

    distance = [INF]*(n+1) # 최단거리 테이블 초기화

    distance[start] = 0 # 출발 노드에서의 최단거리는 0

    q = []

    heapq.heappush(q,(0,start))

    while q:
        d, current = heapq.heappop(q) # 방문하지 않은 노드 중에서 가장 거리가 짧은 노드를 선택
        
        if distance[current] < d: # 이미 선택된 노드는 Pass
            continue

        for node, cost in graph[current]: # 선택한 노드에서 이동할 수 있는 다른 노드와 비용
            new_cost = d + cost # 새로운 거리 = 현재 노드까지의 최단거리 + 현재 노드에서 다음 노드까지의 거리
        
            if new_cost < distance[node]: # 새로운 거리가 다음 노드의 거리보다 짧을 경우
                distance[node] = new_cost # 최단거리 갱신
                heapq.heappush(q,(new_cost,node)) # 방문할 노드에 추가

    return distance # 시작 노드로부터 다른 노드까지의 최단거리가 저장된 1차원 리스트 반환

for i in range(1,n+1): # ( O(N * E * LogV) ) = 10^3 * 10^4 * log(10^3)
    go = dijkstra(i) # 1번부터 N번 마을까지 각각 다른 마을까지의 최단거리 구하기 ( O(E * LogV) )
    total_length[i] = go[x]

back = dijkstra(x) # X 마을에서부터 다른 마을까지 돌아가는 최단거리 구하기

for i in range(1,n+1):
    total_length[i] += back[i] # 왕복거리를 구해야 하므로 X 마을에서부터 돌아가는 최단거리 더해주기

print(max(total_length[1:]))

 

이번 문제는 N개의 마을에서 X 마을까지 최단거리로 이동하고 집으로 돌아온다고 가정했을 때, 왕복이 가장 긴 경로의 소요 시간을 구하는 문제이다.

 

처음에 이 문제를 보았을 때는 모든 노드들을 기준으로 다른 노드들까지의 최단 거리를 구하는 문제라고 생각하여 '플로이드 워셜 알고리즘'을 떠올렸고, 실제로 코드로도 작성했었다.

 

하지만 플로이드 워셜 알고리즘의 시간복잡도는 O(V^3)이므로 10^9개의 연산으로 시간초과가 발생하게 되었다.

 

따라서 한 지점에서부터 다른 지점들까지의 최단 거리를 구할 수 있는 '다익스트라 알고리즘'을 활용하여 다음과 같은 방식으로 풀이하여야 한다.(한 노드당 O(E Log V)의 시간복잡도를 가지므로 약 10^7개의 연산으로 시간초과가 발생하지 않음)

1. N개의 마을 각각에서부터 다른 마을로의 최단거리를 구한 후 X 마을로 가는 최단거리를 구한다. (go[i])
2. X번 마을에서 집으로 되돌아가는 최단거리를 구한다. (back[x])
3. 왕복 최단거리를 구해야 하므로 두 거리를 더해준다.
4. 최댓값을 출력한다.

Heap 자료구조를 이용한 개선된 다익스트라 알고리즘을 복습해볼 수 있었던 문제였다 :)