[Python] [Programmers] 배달(12978)

💡 문제 해결

1. 간선의 정보를 탐색
2. 양방향 간선이기 때문에 양쪽의 노드에 간선 정보를 함께 저장
3. 각 노드별 가장 큰 수를 저장할 dict인 distance를 생성
4. 시작점을 기준으로 BFS
5. 출발점과 노드의 거리를 가장 짧은 값으로 갱신해주며 진행
6. distance의 key, value를 확인하여 value가 K보다 작은 노드의 개수를 출력

📌 대부분의dijkstra문제는 heap을 사용하지만, 이 문제는 노드와 간선의 개수가 작아 굳이 heap을 사용할 필요 X

🧾 문제 설명

N개의 마을로 이루어진 나라가 있습니다. 
이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 
각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 
서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 
도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 
현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 
각 마을로부터 음식 주문을 받으려고 하는데, 
N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다.
마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때,
음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.

문제보기

🖨 입출력

📝 풀이

from collections import deque

def solution(N, road, K):
    answer = 0

    nodes = {}
    for v1, v2, dis in road:
        nodes[v1] = nodes.get(v1, []) + [(v2, dis)]
        nodes[v2] = nodes.get(v2, []) + [(v1, dis)]

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

    # 1번 노드와의 거리 저장
    deq = deque([1])
    while deq:
        current_node = deq.popleft()
        for next_node, dis in nodes[current_node]:
            if distance[next_node] > distance[current_node] + dis:
                distance[next_node] = distance[current_node] + dis
                deq.append(next_node)

    answer = len([True for val in distance.values() if val <= K])

    return answer

• 출처: Programmers
• 링크: https://programmers.co.kr/learn/courses/30/lessons/12978