배달 (python)

프로그래머스 문제 배달 - LV3

https://programmers.co.kr/learn/courses/30/lessons/12978
다익스트라 기본 문제

👀 깃헙 소스

문제설명위 그림에서 1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 마을까지는 3 이하의 시간에 배달할 수 있습니다. 그러나 3번 마을까지는 3시간 이내로 배달할 수 있는 경로가 없으므로 3번 마을에서는 주문을 받지 않습니다. 따라서 1번 마을에 있는 음식점이 배달 주문을 받을 수 있는 마을은 4개가 됩니다.
마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.

입출력 예

N	road								K	result
5	[[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]]		3	4
6	[[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]]	4	4

솔루션
다익스트라 알고리즘을 사용하는 문제로 노드를 탐색하면서 거리를 갱신한다.
출발노드는 거리가 0, 나머지 노드는 무한대로 설정해주고
BFS로 인접 노드를 탐색한다. 이때 현재 노드에서 노드간의 거리를 더해준 값이 저장되어 있는 거리 값 보다 작으면 갱신해주고 que에 노드를 넣어준다.

# nodes
{1: [(2, 1), (4, 2)], 2: [(1, 1), (3, 3), (5, 2)], 3: [(2, 3), (5, 1)], 5: [(2, 2), (3, 1), (4, 2)], 4: [(1, 2), (5, 2)]}

# dist, que
{1: 0, 2: inf, 3: inf, 4: inf, 5: inf}	deque([1])
{1: 0, 2: 1, 3: inf, 4: inf, 5: inf} 	deque([2])
{1: 0, 2: 1, 3: inf, 4: 2, 5: inf} 	deque([2, 4])
{1: 0, 2: 1, 3: 4, 4: 2, 5: inf} 	deque([4, 3])
{1: 0, 2: 1, 3: 4, 4: 2, 5: 3} 		deque([4, 3, 5])

코드

# 파이썬
from collections import deque

def solution(N, road, K):
    nodes = {}
    dist = { i:float('inf') if i != 1 else 0 for i in range(1, N+1) }
    for v1, v2, d in road:
        nodes[v1] = nodes.get(v1, []) + [(v2, d)]
        nodes[v2] = nodes.get(v2, []) + [(v1, d)]
    que = deque([1])
    
    while que:
        cur_node = que.popleft()
        for nxt_node, d in nodes[cur_node]:
            if dist[nxt_node] > dist[cur_node] + d:
                dist[nxt_node] = dist[cur_node] + d
                que.append(nxt_node)

    return len([True for dist in dist.values() if dist <= K])

// 자바스크립트
function solution(N, road, K) {
    const [START_NODE, NODE_LEN] = [1, N];
    let [dist, nodes] = [{}, {}];
    let que = [START_NODE];
    // 거리 설정
    for (let i = 1; i <= NODE_LEN ;i++) {
        dist[i] = i === START_NODE ? 0 : Infinity;
    }
    // 노드별 거리 셋팅
    for (let [v1, v2, d] of road) {
        nodes[v1] = (nodes[v1] || []).concat([[v2, d]]);
        nodes[v2] = (nodes[v2] || []).concat([[v1, d]]);
    }
    // 탐색
    while(que.length > 0) {
        const curNode = que.shift()
        for (let [nxtNode, d] of nodes[curNode]) {
            const newDist = dist[curNode] + d;
            if (dist[nxtNode] > newDist) {
                dist[nxtNode] = newDist
                que.push(nxtNode)
            }
        }
    }
    return Object.values(dist).filter(x => x <= K ).length;
}

팁

# nodes 셋팅
nodes = {}
for v1, v2, d in road:
    nodes[v1] = nodes.get(v1, []) + [(v2, d)]
    nodes[v2] = nodes.get(v2, []) + [(v1, d)]

# dist 셋팅
dist = { i:float('inf') if i != 1 else 0 for i in range(1, N+1) }