[프로그래머스] 배달.py

import math
from collections import deque

def bfs(start, maps, distance, K):
    queue = deque()
    queue.append(start)
    
    # 처음 출발한 도시의 distance는 0
    distance[start] = 0
    
    while queue:
        y = queue.popleft()
        for x in range(1, len(maps)):
            # 도착할 수 있는 도시인 경우
            if maps[y][x] != 0:
                # 해당 마을까지의 거리가 현재까지의 거리 + 이동할 때 걸리는 거리보다 작다 
                # 현재까지의 거리 + 이동할 때의 거리가 K보다 작다 (문제 조건)
                if distance[x] > distance[y] + maps[y][x] and distance[y]+maps[y][x] <= K:
                    distance[x] = distance[y] + maps[y][x]
                    queue.append(x)
    
    # distance 값 중 K보다 작은 값의 개수만 리턴한다.
    return len([i for i in distance if i <= K])
    
                    
def solution(N, road, K):
    # 시작지점 1에서부터 해당 마을까지의 거리. 
    # 초기값을 inf로 설정하고, 계산한 거리가 distance[마을]보다 작으면 distance를 업데이트해준다.
    distance = [math.inf for _ in range(N+1)]
    
    # 마을 그래프 그리기
    maps = [[0 for _ in range(N+1)] for _ in range(N+1)]
    for frm, to, w in road:
        # 0이면 초기화한 값 그대로이므로 w값을 넣어준다
        if maps[frm][to] == 0 and maps[to][frm] == 0:
            maps[frm][to], maps[to][frm] = w, w
        else:
            # 중복된 값이 있을 경우, 가장 작은 weight만 사용한다.
            if w < maps[frm][to]:
                maps[frm][to], maps[to][frm] = w, w
    
    return bfs(1, maps, distance,K)