dict
인 distance
를 생성BFS
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
오오 코드 깔끔하네요! 도움 많이 되었어요!!