문제
배달
- 1번 노드에서 N개의 각 노드로 음식 배달을 진행한다. 음식 배달 시 각 노드에 도달할 수 있는 최단 경로를 구하고, 해당 최단 경로가 K 이하인 노드의 개수를 answer로 리턴해라.
- N : 총 노드의 개수, K : 배달 가능한 최대 경로
- 시작 지점 : 노드 1
그래프
입출력 예시
소스코드
import heapq
INF = int(1e9)
def solution(N, road, K):
answer = 0
distance = [INF]*(N+1)
graph = [[] for _ in range(N+1)]
for r in road:
graph[r[0]].append((r[1], r[2]))
graph[r[1]].append((r[0], r[2]))
queue = []
start = 1
heapq.heappush(queue, (0, start))
distance[start] = 0
while queue:
dist, now = heapq.heappop(queue)
if distance[now] < dist:
continue
else:
for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(queue, (cost, i[0]))
for i in distance:
if i <= K:
answer += 1
return answer
실행 결과