[백준 알고리즘] 14221번: 편의점 (Python)

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

14221번: 편의점

 

소스코드

import sys
import heapq as hq
input = sys.stdin.readline

def dijkstra():
  q = []
  min_dis = [float('inf') for _ in range(n+1)]
  for store in stores: # 편의점의 위치를 한번에 우선순위 큐에 넣어줌 
    hq.heappush(q,[0,store])
    min_dis[store] = 0

  while q:
    cur_dis,cur_node = hq.heappop(q)

    if min_dis[cur_node] < cur_dis:
      continue

    for next_node,next_dis in graph[cur_node]:
      if min_dis[next_node] > next_dis + cur_dis:
        min_dis[next_node] = next_dis + cur_dis
        hq.heappush(q,[next_dis+cur_dis,next_node])

  return min_dis

n,m = map(int,input().split())
graph = [[]for _ in range(n+1)]
for _ in range(m):
  a,b,c = map(int,input().split())
  graph[a].append([b,c])
  graph[b].append([a,c])

p,q = map(int,input().split())
homes = list(map(int,input().split()))
homes.sort() # 거리가 같으면 정정 번호가 낮은 것을 출력하기 위해 오름차순 정렬
stores = list(map(int,input().split()))
ans = float('inf')

t = dijkstra()
for i in homes:
  if ans > t[i]:
    ans = t[i]
    result = i
    
print(result)

 

풀이

★ 문제를 푸는데 계속 30%에서 시간초과가 나서 해결하는 데 시간이 걸렸던 문제였습니다 ! 

 

★ 제 처음 접근법은 편의점의 위치마다 다익스트라를 진행해서 집 후보들과 편의점을 간의 거리를 구해주는 방식이었습니다. 이러면 n이 증가함에 따라 계속해서 다익스트라를 수행해야 하기에 당연히 시간복잡도가 높아질 수 밖에 없습니다.

 

★ 그렇기에 모든 편의점의 위치를 우선순위 큐안에 일단 넣어준 뒤, 다익스트라를 수행하면 한번의 구현으로 답을 출력할 수 있습니다 !!