[백준] 1238번: 파티 문제 풀이 파이썬
문제 링크
https://www.acmicpc.net/problem/1238
이번 문제의 태그는 다익스트라, 나에겐 생소한 방식이었기 때문에 다익스트라가 뭔지에 대해 먼저 공부할 필요가 있었다.
다익스트라란?
하나의 정점에서 다른 정점들까지의 최단 거리들을 찾는 최단 경로 알고리즘의 일종이다.
이 때, 힙큐를 함께 사용하여, 해당 정점에서 연결된 정점들 중 거리가 가장 짧은 경로 먼저 계산을 한다.
이렇게 하면 이미 계산딘 경로의 길이보다 더 긴 거리가 있을 시에 스킵할 수 있다.
풀이 방식
- 그래프를 이용하여 각 각 마을간의 경로와 거리를 저장한다.
- 다익스트라를 이용해 각 마을에서 다른 마을들로 가는 최소 거리들을 계산 후,파티를 하는 마을의 거리를 리턴한다.
- 반대로 파티를 하는 마을에서 각 마을로 가는 최소 거리들을 계산 후, 본인의 마을로 가는 거리를 리턴한다.
- 각 마을별로 반복하여 왕복 거리(2번+3번)의 최대값을 구한다.
전체 코드
from sys import stdin
from sys import maxsize
import heapq
N, M, X = map(int, stdin.readline().split())
graph = {}
for i in range(1, N+1):
graph[i] = []
# 각 마을간의 경로와 거리를 그래프에 저장
for _ in range(M):
start, end, T = map(int, stdin.readline().split())
graph[start].append([end, T])
def dijkstra(i):
queue = []
distance = [maxsize] * (N+1)
# 현재 위치와 이동한 거리 큐, distance에 저장
heapq.heappush(queue, (0, i))
distance[i] = 0
while queue:
# 거리가 짧은 마을의 노드 먼저 계산
dist, village = heapq.heappop(queue)
# 해당 마을의 거리가 이미 최소 거리이면 스킵
if distance[village] < dist:
continue
# 해당 마을에서 연결된 마을들에 대해
for node_village, node_dist in graph[village]:
# 연결된 마을들까지의 거리는 현재 거리 + 해당마을까지의 거리
cost = dist + node_dist
# 연결된 마을까지의 거리보다 cost가 작으면 거리 변경
if distance[node_village] > cost:
distance[node_village] = cost
heapq.heappush(queue, (cost, node_village))
return distance
ans = 0
for i in graph:
if i == X:
continue
# 각 마을에 사는 아이들의 파티 왕복시간 중 최대값 계산
ans = max(dijkstra(i)[X] + dijkstra(X)[i], ans)
print(ans)
Author And Source
이 문제에 관하여([백준] 1238번: 파티 문제 풀이 파이썬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hyuntall/백준-1238번-파티-문제-풀이-파이썬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)