[백준] 편의점(python)

백준, 편의점

14221번: 편의점

TL;DR

• 다익스트라 알고리즘(Dijstra algorithm)

문제 요약

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

- 편의점과 집이 정점, 각 정점의 가중치가 있는 그래프에서 최단 거리 지점을 찾는 문제이다.

- 편의점 노드와 집 노드가 따로 분리되어 있기 때문에 이를 사용하여 거리를 계산해야 한다.

입출력 형태

입출력 예시

 

예시 1 :: 주어진 문제에서 집 정점은 1, 2, 3. 편의점 정점은 4, 5, 6으로 주어진다.

- 편의점 4, 5, 6에서 각 집 1, 2, 3까지의 최단 경로는 1이다. 이 중 가장 집의 정점 번호가 낮은 1이 정답으로 출력된다.

풀이

이 문제는 다익스트라를 이용해서 풀어야 한다. 단, 기존의 정점 간의 구분 없이 단순히 두 정점 사이의 최단 경로를 구하던 다익스트라와 달리 편의점으로부터 집 까지의 최단 경로들을 갱신하며 구해야 하기 때문에 중간 과정을 필요로 한다.

import sys, heapq
from collections import defaultdict

N, M = map(int, sys.stdin.readline().split())
graph = defaultdict(list)
for _ in range(M):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append([b, c])
    graph[b].append([a, c])
P, Q = map(int, sys.stdin.readline().split())
homes = list(map(int, sys.stdin.readline().split()))
stores = list(map(int, sys.stdin.readline().split()))

dists = [1_000_000_000_001] * (N + 1)
min_dist, answer = 1_000_000_000_001, 0

for store in stores:
    heap = [(0, store)]
    min_dists = [1_000_000_000_001] * (N + 1)
    min_dists[store] = 0

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

        if node in homes: # 최단 경로를 갱신했기 때문에 더 이상 수행하지 않음
            break
        if min_dists[node] < d:
            continue
        
        for v, w in graph[node]:
            alt = d + w
            if min_dists[v] > alt and v != store: # 집 노드들의 최단 경로 갱신
                min_dists[v] = alt
                heapq.heappush(heap, (alt, v))
            dists[v] = min(dists[v], min_dists[v]) # 전체 최단 경로 갱신

for home in homes:
    if min_dist > dists[home]:
        min_dist = dists[home]
        answer = home

print(answer)

 

풀이가 상당히 길고 복잡하다. 코드의 처음부터 stores를 선언 및 할당하는 구문까지는 문제에서 주어지는 입력을 처리하는 구문이기 때문에 별 특이할 것이 없기 때문에 그 아래 코드부터 하나씩 확인해보겠다.

 

dists : 모든 경우의 최단 경로를 저장하기 위한 리스트이다. 코드에서는 각 편의점들에 대해서 집까지의 최단 경로를 계산하게 된다. 즉 편의점이 3개라면 3가지 최단 경로가 나오게 된다. 이 중 가장 짧은 거리를 이 리스트에서 저장한다.

min_dist, answer : 정답을 출력하기 위해 선언한 변수들이다. min_dist는 최종적으로 계산된 거리인 dists에서 최단 경로를 저장하기 위한 변수이고, answer은 그 때의 정점을 저장하기 위한 변수이다.

 

각 편의점에서 각 집까지의 최단 경로들을 다익스트라 알고리즘을 통해 계산한다.

min_dists는 하나의 편의점에서 각 집까지의 최단 경로를 저장한다.

heapq를 통해 경로를 갱신해나간다. 방문한 점이 집 정점이라면 수행을 중단한다. 그 이유는 뒷 부분에 등장한다. 그리고 최단 경로가 이미 있는 경우는 연산을 건너뛴다. 이미 최단경로이기 때문에 별도로 갱신할 필요가 없기 때문이다.

방문 정점에서 인접 정점들과 비교를 한다. 이 때, 정점이 편의점이 아닌 집일 경우 해당 지점의 최단 경로를 갱신한다. 앞서 방문한 정점이 집 정점이라면 수행을 중단하는 이유는 이미 이 구문에서 최단 경로를 갱신하기 때문이다. 최단 경로를 갱신하고 난 뒤에는 heapq에 삽입하고 전체 최단 경로를 저장할 dists 또한 갱신해준다.

이 과정을 거치고 나면 dists에는 각 편의점으로부터 집까지의 최단 경로들이 저장되게 된다. 이제 집 정점들을 확인하며 최단 경로일 때 가장 작은 집을 answer에 할당해주면 된다.

 

풀이를 정리하자면

- 각 편의점과 집들 사이의 최단 경로를 갱신한다.

- 갱신된 각 편의점들과 집 사이의 최단 경로를 하나로 만든다.

- 하나로 만들어진 최단 경로들에서 가장 낮은 정점을 찾아내어 출력한다.

로 정리할 수 있겠다.

참고

이 코드는 같이 알고리즘 스터디를 진행하는 대훈님에게 질문한 후 푼 풀이이다.

daehoon12 (DaeHoon) - velog