[Python 문제 풀이] 프로그래머스 '배달'

Programmers Lv.2 '배달' 파이썬 코드 및 풀이
Dijkstra 알고리즘을 몰라도 DP적으로 접근하면 풀 수 있다. 

 

접근

 출발지가 정해져 있고 출발지에 인접하지 않은 지점은 반드시 어딘가를 거쳐서 온다고 확신할 수 있다. 그렇다면 거쳐온 중간지점까지 누적된 거리에 추가로 한 단계의 거리만 추가하면 출발지로부터의 거리가 된다. 어느 한 위치의 관점에서 봤을 때 여기서 주변 지점으로 더 나아갈 수 있는지 없는지만 확인하면 된다. 그리고 도달 가능했던 지점들에 대해서 도달가능한 지점이 없을 때까지 이전 수행결과를 전파시키면 된다.

 

 이는 큰 문제를 작은 부분 문제로 쪼개 생각하는 DP와 완벽히 동일하다. 그도 그럴게 Dijkstra가 애초에 DP의 특수한 케이스이다. 현실에 적용하기 안성맞춤인 알고리즘이다 보니 유명한 것.

의사코드

1. 각 노드에 도달할 수 있는 누적 최단거리를 저장하기 위해 노드의 수에 대응되는 1차원 배열을 만든다.

2. 효율성을 위해 각 노드 간의 연결관계를 접근하기 쉬운 자료형태로 바꾼다.

3. 연결관계를 기록한 자료를 순회하면서 더 가까운 거리로 왔을 경우 최단거리를 갱신하고 배달가능 마을로 기록한다.

4. 갱신된 노드들에 대해서만 다시 반복한다.

구현

from collections import deque
def solution(N, road, K):
    routes = [{} for _ in range(N+1)]
    distance = [K+1] * (N+1)
    distance[1] = 0
    available = {1}

    for n1, n2, d in road:
        if n2 not in routes[n1] or routes[n1][n2] > d:
            routes[n1][n2] = d
            routes[n2][n1] = d

    neighbors = deque([1])
    
    while neighbors :
        n1 = neighbors.popleft()
        for n2, d in routes[n1].items() :
            if distance[n2] > d + distance[n1] :
                distance[n2] = distance[n1] + d
                neighbors.append(n2)
                available.add(n2)
                
    return len(available)