[Programmers 12978] 배달

문제

LV2 [Programmers 12978 - 배달]

문제 풀이 방법

최단경로 알고리즘 문제를 집중적으로 공부하고 있었기 때문에 바로 다익스트라 알고리즘을 이용하여 풀이할 수 있었다.
이 문제도 예전에 이미 풀이한 문제였지만 예전에는 다익스트라 알고리즘을 정확하게 모르고 풀이했었는데, 이번에는 확실하게 공부하고 이해하고 풀어서 전보다 더 간단하고 가독성 좋게 푼 것 같다!

1. graph와 distance를 각각 N+1만큼 초기화한다.

   graph를 표현하는 방법에는 크게 인접행렬과 인접 리스트 이렇게 2가지가 있는데, 여기서는 인접 리스트를 사용하여 그래프를 표현하였다.

   distance는 1번 노드부터 각 노드까지의 거리를 저장할 배열로 INF(무한)으로 초기화한다.

   N+1개를 생성하는 이유는 노드번호가 1부터 시작하기 때문에 뒤에서 좀 더 가독성 좋은 코드를 쓰기 위해서이다. 그래서 0번째 배열은 사용되지 않는다.

2. 우선순위 큐를 선언하고 (시작노드의 거리, 시작노드)를 큐에 넣어준다.

   매 단계마다 방문하지 않은 노드 중에서 가장 거리가 짧은 노드를 선택해야 되기 때문에 우선순위 큐를 사용한다. 이 때, 우선 순위의 기준은 튜플의 0번째 인덱스(=거리)이다.

3. 큐가 빌때까지 다음을 반복한다.

   1. 큐에서 가장 거리가 짧은 노드(node)를 뽑는다.
   2. 만약 현재 거리 리스트(distance)에서 해당 노드의 거리(distance[node])가 뽑은 노드의 거리(dist)보다 더 작다면 이미 방문했다는 의미이므로 아래를 수행하지 않고 넘어간다.
   3. 뽑은 노드와 인접하게 연결된 노드들을 for문을 돌면서 순회한다.
      1. 현재 노드(node)를 거쳐서 가는 경우의 거리를 계산하여 cost에 저장한다.
      2. 만약, 현재 거리 리스트(distance)보다 cost가 작다면 거리 리스트를 업데이트 해주고, 큐에 (cost, n)를 추가해준다.

풀이 코드

Python

import heapq

def solution(N, road, K):
    INF = int(1e9)
    graph = [[] for _ in range(N+1)]
    distance = [INF] * (N+1)
    for a,b,c in road:
        graph[a].append([b, c])
        graph[b].append([a, c])

    q = []
    heapq.heappush(q,(0,1))
    distance[1] = 0
    while q:
        dist, node = heapq.heappop(q)
        if distance[node] < dist:
            continue
        for n,d in graph[node]:
            cost = d + dist
            if cost < distance[n]:
                distance[n] = cost
                heapq.heappush(q, (cost, n))

    answer = 0
    for i in range(1,N+1):
        if distance[i] <= K:
            answer += 1
    return answer