BAEKJOON #1238 파티 (Graph, 최단경로) - python

nathan·2021년 8월 11일

알고리즘문제

목록 보기

35/102

파티

시간 제한	메모리 제한
1초	128MB

문제

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))