백준 1238 문제 풀이 python

🐒 파티

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

✍ 나의 풀이

import heapq
import sys
import math

input = sys.stdin.readline

N, M, X = map(int, input().split())
#N명의 학생, M개의 도로, 파티장소 X
#집에서 X에 갔다가 다시 집으로 가는 최단시간중 최대값?


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

for _ in range(M):
    # 시작점, 끝점, 소요시간
    a,b,c = map(int, input().split())
    graph[a].append((b,c))

#for 문 돌려서, x에 도착시키고, x부터 집으로 함수실행하고 최대값 찾기?
time = [0] * (N+1)

def dijkstra(start):
    cost = [math.inf] * (N+1)
    q = []
    heapq.heappush(q,(0,start))
    cost[start] = 0
    while q:
        time, now = heapq.heappop(q)
        if time > cost[now]:
            continue
        for i in graph[now]:
            if cost[i[0]] > i[1] + time:
                cost[i[0]] = i[1] + time
                heapq.heappush(q,(cost[i[0]],i[0]))
    return cost


for i in range(1,N+1):
    toparty = dijkstra(i)
    time[i] = toparty[X]

# 파티끝나고 각자 집으로

tohome = dijkstra(X)
for i in range(1,N+1):
    time[i] = time[i] + tohome[i]

print(max(time))

26분만에 풀 수 있었던 문제였다.
의도한대로 문제가 풀려서 재밌게 풀 수 있었다.

🧠 문제 이해

N개의 마을에 아이가 한명씩 산다.
X마을에 파티가 열리면 아이들이 M개의 도로를 이용해 X마을에 왔다가 다시 집으로 돌아간다.

이때 아이들은 최소비용으로 도로를 통과하는데
아이들 중에서 가장 많은 비용을 지불한 아이를 출력해야한다.

지문에는 "이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다." 라고 명시되어있는데 나에게 힌트로 다가왔다.

나는

1. for문으로 다익스트라 알고리즘을 실행시켜서 모든 아이들이 X마을에 도착하는 최소비용을 저장하고
2. X마을에서 각 마을에 도착하는 최소비용을 구하고,
3. 1과 2를 합하여 최대값을 나타내는 마을을 출력

해야겠다고 생각했다.

설계한대로 정답이 나와서 기분이 좋았다☺️