[프로그래머스] 배달

programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달

 

[풀이]

1부터 q에 append하고, while문을 돌며 pop을 한다.

pop을 한 것과 연결되어 있는 것중에서, 이미 계산한 거리보다 지금 보고있는 연결 마을을 통해서 가는것이 더 짧은 경우 -> distance를 update

 

from collections import deque

def solution(n, road, k):
    INF=int(1e9)

    distance=[INF]*(n+1) # 1번 마을부터 각 마을까지 떨어져있는 거리
    distance[1]=0

    graph=[[INF]*(n+1) for _ in range(n+1)]
    for i in road:
        graph[i[0]][i[1]] = min(graph[i[0]][i[1]], i[2])
        graph[i[1]][i[0]] = min(graph[i[1]][i[0]], i[2])

    q=deque()
    q.append(1)

    while q:
        now=q.popleft()
        for next in range(1,n+1):
            if graph[now][next] != INF and distance[next] > distance[now]+graph[now][next]:
                q.append(next)
                distance[next] = distance[now]+graph[now][next]

    result=0
    for i in range(len(distance)):
        if distance[i] <= k:
            result += 1

    return result