[Gold IV] 편의점 - 14221 (다익스트라)

[Gold IV] 편의점 - 14221

문제 링크

성능 요약

메모리: 132472 KB, 시간: 424 ms

분류

다익스트라(dijkstra), 그래프 이론(graphs)

문제 설명

영선이는 이사할 일이 생겨 집을 알아보고 있다. 영선이는 혼자 살기 때문에, 편의점에서 대충 때울 때가 많아, 집을 고르는 기준을 편의점과의 거리가 가장 가까운 곳으로 하려한다.

영선이가 이사할 도시는 정점과 간선으로 표현할 수 있는데, 이사가려 하는 집의 후보들과 편의점은 정점들 위에 있다.

영선이는 캠프 강사 준비로 바쁘므로, 대신하여 집을 골라주자. 만약 거리가 같은 지점이 여러 개라면 정점 번호가 가장 낮은 곳으로 골라주자.

입력

처음 줄에는 정점의 개수 n, 간선의 개수 m이 주어진다.(2 ≤ n ≤ 5,000, 1 ≤ m ≤ 100,000) 다음 m줄에는 a,b,c가 주어지는데 이는 a, b를 잇는 간선의 거리가 c라는 것이다.(1 ≤ a, b ≤ n, 1 ≤ c ≤ 10,000)

다음 줄에는 집의 후보지의 개수 p와 편의점의 개수 q가 주어진다.(2 ≤ p+q ≤ n, 1 ≤ p, 1 ≤ q) 다음 줄에는 집의 후보지들의 정점번호, 그 다음줄에는 편의점의 정점번호가 주어진다. 집의 후보지와 편의점은 서로 겹치지 않는다.

출력

편의점으로부터 가장 가까운 지점에 있는 집 후보의 정점 번호를 출력하시오. 만약 거리가 같은 곳이 여러 군데라면 정점 번호가 낮은 곳을 출력하시오.

다익스트라는 하나의 시작 정점으로 부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘이다. 처음 보면 겁먹거나 어려워서 기피하게 되기도 하는 알고리즘. 내가 그랬지만 이제 슬 풀어볼 때가 된 것 같다.

import sys, heapq
n, m = map(int, input().split()) 
inf = float('inf')
graph = [[] for _ in range(n+1)]
for i in range(m):
  a, b, dis = map(int,input().split())
  graph[a].append((b, dis))
  graph[b].append((a, dis))
p, q = map(int,input().split())
homes = sorted(list(map(int, input().split())))
stores = list(map(int, input().split()))

dists = [inf] * (n+1)
heap = []

for i in stores:
  heapq.heappush(heap, (0, i))
  dists[i] = 0

while heap:
  distance, node = heapq.heappop(heap)

  if dists[node] < distance:
    continue

  for v, w in graph[node]:
    sum_distance = distance + w
    if dists[v] > sum_distance:
      dists[v] = sum_distance
      heapq.heappush(heap, (sum_distance, v))
    
tmp = homes[0]
answer = dists[tmp]
for i in homes:
  if dists[i] < answer and dists[i] != 0:
    tmp = i
    answer = dists[i]
print(tmp)

푼 기간 (2~3일)

시간초과에서 많이 헤매서 몇 일 고민하고 여러 피드백을 들은 끝에 해결할 수 있었다.

문제만 언뜻 보면, 집을 기준으로 해서 모든 편의점과의 거리를 비교하여 최단거리를 구하는 함정에 빠질 수 있다.(나도 마찬가지였다.)

그러나, 모든 편의점 기준으로 힙에 넣어 각각의 집 정점까지의 최단거리를 구해주면 쉽게 풀리는 문제였다.

첫 번째로 해당 풀이법을 생각하지 못해서 오래 걸렸고, 두 번째로 편의점을 기준으로 생각한 후에는 모든 편의점을 한 번에 힙에 넣을 생각을 못하고 하나씩 넣어서 시간초과를 겪어야 했다.

문제가 너무 안풀려서 피드백을 더 받은 결과, 모든 편의점에서 집까지의 최단 거리가 필요하니 출발점을 모든 편의점의 정점으로 해야하는 것이었다. 이 피드백을 듣고나서 문제점이 뭐였는지 확실하게 이해하고, 문제를 해결할 수 있었다.