백준18223 - 민준이와 마산 그리고 건우 (데이크스트라) Python

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

해당 문제는 최단 경로라는 그 말마따나, 최단 경로 문제를 해결하기에 용이한 다이크스트라 알고리즘으로 접근했다.

풀이 방식은 다이크스트라 알고리즘을 구현할 수 있다면 어렵지 않은데, 

민준이가 곧장 마산으로 가는 경우가 민준이가 건우 위치를 경유하여 마산으로 가는 경우를 비교하여 답안을 출력하면 된다.

 

전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()
import heapq

def solution (data) :
  arr = [list(map(int, x.split())) for x in data]
  n,_,p = arr.pop(0)
  graph = [[] for _ in range(n+1)]
  for s,e,c in arr :
    graph[s].append((c,e))
    graph[e].append((c,s))

  route1 = dijkstra(graph,1)
  route2 = dijkstra(graph,p)

  print('SAVE HIM' if route1[n] >= route1[p] + route2[n] else 'GOOD BYE')

def dijkstra (graph, start) :
  distances = [float('inf') for _ in range(len(graph))]
  distances[start] = 0

  pq = []
  heapq.heappush(pq, (0,start))

  while pq :
    dist, node = heapq.heappop(pq)
    if dist > distances[node] : continue

    for next_dist, next in graph[node] :
      sum_dist = next_dist + dist
      if distances[next] > sum_dist : 
        distances[next] = sum_dist
        heapq.heappush(pq, (sum_dist, next))

  return distances

solution(input_data)