Lv3 배달

문제

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

풀이

다익스트라 알고리즘을 통해 구현한다.

코드

def solution(N,road,K):
    answer = 0
    d = {}
    for i in range(N):
        d[i+1] = []
    for r in road:
        d[r[0]].append((r[1],r[2]))
        d[r[1]].append((r[0],r[2]))
    #shortest distance
    sd = [500000 for _ in range(N)]
    sd[0] = 0
    visited = [1]
    while len(visited) < N:
        curr = visited[-1]
        reachable = [item for item in d[curr] if item[0] not in visited]
        for item in reachable:
            before = sd[item[0]-1]
            now = sd[curr-1] + item[1]
            if now < before:
                sd[item[0]-1] = now
        min_value = 500000
        min_index = -1
        for i in range(N):
            if i+1 in visited:
                continue
            if sd[i] <= min_value:
                min_value = sd[i]
                min_index = i
        visited.append(min_index+1)
    for i in range(N):
        if sd[i] < K + 1:
            answer += 1
    
    return answer