[백준 1238번] 파티 (Python/파이썬)

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

1238번: 파티

다익스트라 알고리즘을 배우고 적용하려는 참에 좋은 문제가 있어서 포스팅한다.

아마 well known일거 같긴한데 처음 접하는 문제라 기록에 남겨 놓는다.

시간복잡도가 그리 중요하지 않은 문제라 두가지 방법으로 모두 통과되어서 두가지 모두 소개하려고 한다.

1. N회 다익스트라

특정 마을에서 목적지 X까지 가야하므로 N-1번의 다익스트라가 필요하다.

X에서 다시 마을로 돌아와야하므로 한번의 다익스트라면 충분하다.

총 N번의 다익스트라 실행

2. 2회 다익스트라

특정마을에서 목적지 X까지 가는 것을 관점을 뒤집는 것이다.

각각의 마을에서 X까지 가는 단방향 길이 있다.

근데 각각의 마을에서 X까지 가는 시간은 단방향 길을 역방향 길로 바꾸고 X에서 각각의 마을로 가는 시간을 측정하는 것과 같다.

따라서 단방향 간선을 뒤집은 역방향 단선 인접리스트를 따로 하나더 설정해 놓는다.

그리고 X에서 마을로 가는 다익스트라를 적용하면 각 마을에서 X로가는 경로가 한번에 구해진다.

 

X에서 각 마을로 가는 경로는 1번과 똑같이 1회의 정방향 다익스트라면 충분하다.그래서 총 2회의 다익스트라로 문제를 해결할 수 있다.

 

1번은 단순한 다익이므로 2번만 올린다.

import sys
import heapq
input = sys.stdin.readline
INF = sys.maxsize
N, M, X = map(int,input().split())
adj_go = [[] for _ in range(N+1)]
adj_back = [[] for _ in range(N+1)] ##역방향 단선 
for _ in range(M):
  s, e, t = map(int,input().split())
  adj_go[s].append((e,t))
  adj_back[e].append((s,t))


def dijkstra(start, graph):
  queue = []
  heapq.heappush(queue,(0,start))
  distList = [INF] * (N+1)
  distList[start] = 0
  while queue:
    (pathLength, node) = heapq.heappop(queue)
    if pathLength > distList[node]: continue
    for i in graph[node]:
      distance = pathLength + i[1]
      if distList[i[0]] > distance:
        distList[i[0]] = distance
        heapq.heappush(queue,(distance, i[0]))
  return distList[1:]

dist_go = dijkstra(X,adj_go)
dist_back = dijkstra(X,adj_back)
ans = 0
for i in range(len(dist_go)):
  ans = max(dist_go[i] + dist_back[i],ans)
print(ans)

 

 

 

처음에 시간초과는 1번 방법으로 파이썬의 PriorityQueue를 사용해서 발생했다.

heapq와 PriorityQueue는 속도가 10~30배 정도 차이나니 heapq를 사용하도록 하자.