[프로그래머스] 배달 (파이썬)

📕 문제

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

코딩테스트 연습 - 배달

 

💡 풀이법

1. 연결된 노드와 거리를 담을 연결딕셔너리 dist를 만들어 준다.

2. 각 노드들의 방문유무와 시간을 기록할 방문리스트 visited를 만들어준다.

3. 1번 노드부터 deq에 넣고 노드와 인접한 노드들중 시간이 K보다 작거나 같고, 한번도 방문하지 않았거나 방문했더라도 현재 걸린 시간이 기록된 시간보다 짧으면 visited를 갱신해주고 deq에 노드를 넣어준다.

4. while문이 끝나면 visited에서 0을 제외한 숫자들의 개수를 구한다.

(0은 제한 시간 내에 방문하지 못한 노드이기 때문)

from collections import defaultdict, deque
def solution(N, road, K):
    dist = defaultdict(list)
    for a, b, c in road:
        dist[a].append((b,c))
        dist[b].append((a,c))

    visited = [0 for _ in range(N+1)]
    deq = deque([(1, 0)])
    visited[1] = 1
    while deq:
        x, d = deq.popleft()
        
        for v, w in dist[x]:
            if d + w <= K and (not visited[v] or d + w <= visited[v]):
                deq.append((v, d + w))
                visited[v] = d + w
                
    answer = N+1-visited.count(0)
    return answer