[백준 알고리즘] 13911번: 집 구하기 (Python)

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

13911번: 집 구하기

 

소스코드

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

def dijkstra1():
  q = []
  min_dis = [float('inf') for _ in range(V+1)]
  for i in mac: # 힙 안에서 맥도날드 지점을 다 집어 넣어서 최단거리 한번에 계산
    hq.heappush(q,[0,i])
    min_dis[i] = 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

def dijkstra2():
  q = []
  min_dis = [float('inf') for _ in range(V+1)]
  for i in star: # 힙 안에서 스타벅스 지점을 다 집어 넣어서 최단거리 한번에 계산
    hq.heappush(q,[0,i])
    min_dis[i] = 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

V,E = map(int,input().split())
graph = [[] for _ in range(V+1)]
for _ in range(E):
  u,v,w = map(int,input().split())
  graph[u].append([v,w])
  graph[v].append([u,w])

m,x = map(int,input().split())
mac = list(map(int,input().split()))
s,y = map(int,input().split())
star = list(map(int,input().split()))
k = dijkstra1() # 맥세권인지 확인하는 다익스트라
t = dijkstra2() # 스세권인지 확인하는 다익스트라

ans = float('inf')
for i in range(1,V+1):
  if k[i] == 0 or t[i] == 0:
    continue
  elif k[i] == float('inf') or t[i] == float('inf'):
    continue
  else:
    if k[i] <= x and t[i] <= y:
      result = k[i] + t[i]
      ans = min(ans,result)
    else:
      continue

if ans == float('inf'):
  print(-1)
else:
  print(ans)

 

풀이

★ 문제가 살짝 복잡해 보일수도 있지만 주어진 조건들을 하나하나 만족시키면서 풀어가면 됩니다. 스타벅스 또는 맥도날드가 있는 정점 모두에서 집으로의 최단거리를 구해주면 당연히 시간초과가 나게 됩니다. 그렇기에 저는 다익스트라를 2개 만들어서 하나는 맥도날드까지의 최단거리, 다른 하나는 스타벅스까지의 최단거리를 구해줬습니다.

 

★ 이 때 다익스트라를 계속해서 호출하지 않기 위해 초기 힙안에 맥도날드와 스타벅스가 있는 정점을 각각 전부 집어넣은 뒤, 다익스트라를 돌았습니다. 이럴 경우 한번의 호출만으로 각 집으로부터의 최단거리를 구할 수 있습니다.