백준 1238번 파티 파이썬

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

1238번: 파티

 

내 코드

import heapq
import sys

input = sys.stdin.readline
INF = int(1e9)

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

graph = [[] for i in range(N + 1)]
distance = [INF] * (N + 1) # 최단 거리 테이블을 무한으로 초기화
answer = []

for _ in range(M):
    a, b, c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용(시간)이 c
    graph[a].append((b, c))


def dijkstra(X):
    q = []
    heapq.heappush(q, (0, X))
    distance[X] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))


dijkstra(X)
answer = distance[:]
distance = [INF] * (N + 1)

for i in range(1, N + 1):
    if i != X:
        dijkstra(i)
        answer[i] += distance[X]
        distance = [INF] * (N + 1)

print(max(answer[1:]))

---

 

Review

1. X 에서 다른노드로 가는 모든 시간(cost)계산
-> 다익스트라 알고리즘
-> answer에 최단시간들을 기록

dijkstra(X)
answer = distance[:]
distance = [INF] * (N + 1) # 초기화

 

2. X가 아닌 다른노드에서 X로 가는 시간(cost) 계산
-> 다익스트라 알고리즘
distance[X] 에 X로 돌아가는 최단 시간(cost) 을 i 번째 노드에 더한다.

for i in range(1, N + 1):
    if i != X:
        dijkstra(i)
        answer[i] += distance[X]
        distance = [INF] * (N + 1) # 초기화

1번 + 2번 연산을 진행하고, 그 중 최댓값을 찾으면 가장 오래걸리는 소요시간을 찾을 수 있다.

 

주어진 예제로 그림을 그려 생각해 보자면,

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

# 10

 

⭐️ 1번 과정

결과 : distance = answer = [INF, 1, 0, 3, 7]

 

⭐️ 2번과정

🔥 answer 배열의 i번째 원소에 i 노드에서 2로가는 최단 경로인 distance[2] 를 더해준다면 아래의 결과를 도출해 낼 수 있다.

 

위의 과정을 answer[i] += distance[X] 이 수식으로 일반화를 해줄수 있다.

 

따라서 학생들이 오고 가는데 걸리는 소요시간이 담겨있는 배열은 answer = [1000000000, 5, 0, 9, 10]

얻고자 하는 값은 가장 높은 시간(cost) 이니 max(answer[1:]) 을 해주면 답을 도출 해낼 수 있다.

>>> print(max(answer[1:]))
10