[백준1238&파이썬] 다익스트라를 여러번 사용해서 최장 경로를 얻어보자

# 문제

백준 1238 파티 파이썬 풀이

1238번: 파티

 

# 코드

'''
  - 오고 가야함, X까지 오는건 각각 구하고, X에서 다시 원래 지점까지 가는 방법은 X로 다익스트라 한번만 돌리면 될듯
  - total_distance를 하나 만든다
    - total_distance는 X에서 N까지의 모든 경로를 미리 구해놓는다
    - 이후 N -> X로 가는 최단거리의 값을 구해서 다익스트라를 사용해서 해당 경로에 더해준다.
'''
import sys
from collections import defaultdict
import heapq

graph = defaultdict(list)
# N명 학생, M개의 단방향 도로, X번 마을
N, M, X = map(int,sys.stdin.readline().split())
# print(f"X : {X}")

for _ in range(M) :
  # a->b, weight
  a,b,w = map(int,sys.stdin.readline().split())
  graph[a].append((b,w))


### X -> N(모든 노드)로 가는 COST를 구함 ###
total_distance = [float('inf')] * (N+1)
total_distance[X] = 0
heap = list()
heapq.heappush(heap,(0,X)) # 힙에 초기값을 넣어준다.

while len(heap) != 0 :
  cur = heapq.heappop(heap) # ( sum_weight, vertex )

  if total_distance[cur[1]] < cur[0] : # 굳이 방문할 필요가 없다.
    continue

  for next in graph[cur[1]] : # ( vertex, weight )
    cost = total_distance[cur[1]] + next[1]
    if cost < total_distance[next[0]] :
      total_distance[next[0]] = cost
      heapq.heappush(heap,(cost, next[0]))

# print(f"total_distance : {total_distance}")
### --- total_distance에 경로가 저장 됨 ###


for start in range(N+1) :
  if start == X or start == 0 : # 도착지점이기 때문에 굳이 계산할 필요가 없다.
    continue

  distance = [float('inf')] * (N+1)
  distance[start] = 0
  heap = list()
  heapq.heappush(heap,(0,start))

  while len(heap) != 0 :
    cur = heapq.heappop(heap) # ( sum_weight , vertex )

    if distance[cur[1]] < cur[0] :
      continue

    for next in graph[cur[1]] : # ( vertex, weight )
      cost = distance[cur[1]] + next[1]
      if cost < distance[next[0]] :
        distance[next[0]] = cost
        heapq.heappush(heap,(cost,next[0]))

  # print(start, distance)
  total_distance[start] += distance[X]

total_distance.sort(reverse=True)
print(total_distance[1])

 

# 풀이

• N명의 위치에서 X까지 가는 경로는 N 각각 구해야한다
• X에서 N으로 가는 거리들은 한번에 구할 수 있다.
• 두개를 합해서 최대값을 찾는다.
• 시간 초과가 안난게 신기하다.
  • 다익스트라 알고리즘에서 우선순위 큐를 사용하면 시간 복잡도는 O((E+V)logV)가 됩니다. 여기서 E는 간선의 개수, V는 노드의 개수입니다. 다익스트라 알고리즘에서는 각 노드를 한 번씩 방문하고, 각 노드에서 인접한 간선을 모두 검사합니다. 이 때 우선순위 큐를 사용하면 최단 거리가 가장 짧은 노드를 빠르게 찾을 수 있기 때문에 검사해야 하는 간선의 수가 줄어들어 시간 복잡도가 감소합니다. 이렇게 우선순위 큐를 사용하면 다익스트라 알고리즘의 시간 복잡도를 효율적으로 줄일 수 있습니다.