파티

출처 : 백준 #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명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

입출력 예시

예제 입력 1

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

예제 출력 1

10

풀이

생각

• 직전에 풀었던 문제인 특정거리의 도시 찾기, 최단 경로 문제 등과 매우 유사하다.
• 허나 여기서는 조금 다르게 모든 마을(노드)에서 목적지까지 갔다가 돌아오는 경우를 고려해야한다.
• 그래도 마찬가지로 그래프에서 최단 거리를 구하는 문제이다.
• 최단 거리를 구하는 알고리즘은 다익스트라, 플로이드 워셜 등이 있다.
• 범위가 크기 때문에 O(N^3)의 복잡도를 갖는 플로이드 워셜 알고리즘 보다는 O(ElogV)의 복잡도를 갖는 다익스트라 알고리즘을 활용해 문제를 풀었다.

풀이 설명

• 우선 graph를 n+1 크기로 만든다.
  • 노드의 번호를 인덱스로 그대로 사용하기 위함이다.
• heapq를 이용하여 최소힙을 통해 거리가 짧은 순으로 탐색한다.
• 만약 distance\[node] < dist라면, 즉 해당 노드까지의 거리가 heapq에서 나온 거리보다 짧다면 굳이 아래 과정을 진행하지 않고 다음 heapq의 원소로 차례를 넘긴다.
• distance\[node] < dist가 아니라면, cost를 dist에서 1이 추가된 값으로 업데이트 하고 distance[i]와 비교한다.
• 만약 cost가 더 짧다면, distance[i]를 cost 값으로 업데이트 한다.
• 또한 해당 값을 heapq에 push 한다.

앞의 문제들과 다른점

• 목적지(x)까지 갔다가 돌아와야 하므로, 우선 for문을 통해 모든 노드에 대해서 목적지까지 도달하는 distance를 각각 구한다.
• start가 x일 때는, 목적지에서 각각의 노드로 돌아가는 경우라고 생각한다.
  • 따라서 해당 node 인덱스에 있는 값을 maxTime 리스트의 인덱스를 하나씩 돌며 각각 더해준다.
  • 그리고 max 값을 뽑아내면 된다!

python code

# 백준 1238번 파티 (최단 경로)
from sys import stdin
import heapq


input = stdin.readline

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


def solution(graph, n, x):
    queue = []
    maxTime = [0] * (n+1)
    INF = int(1e9)
    
    distance_x = []
    for start in range(1, n+1):
        distance = [INF] * (n+1)
        heapq.heappush(queue, (0, start))
        distance[start] = 0

        while queue:
            dist, node = heapq.heappop(queue)
            if distance[node] < dist:
                continue
            
            for c in graph[node]:
                cost = dist + c[1]
                if distance[c[0]] > cost:
                    distance[c[0]] = cost
                    heapq.heappush(queue, (cost, c[0]))


        if start != x:  # 도착지점이 출발점이 아닌 경우 ~ start에서 x까지 가는 최단 경로
            maxTime[start] = distance[x]
        else:   # start == x : 도착지점이 출발점인 경우 ~ x에서 start까지 가는 최단 경로
            distance_x = distance

    for i in range(1, n+1):
        maxTime[i] += distance_x[i]

    return max(maxTime)

print(solution(graph, n, x))