프로그래머스 [Lv. 2] 배달 {언어 : Python}

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12978?language=python3

프로그래머스

정답 코드

from collections import deque

def solution(N, road, K):
    answer = 0
    adjL = [[] for _ in range(N+1)]
    for start, to, time in road:
        adjL[start].append((to, time))
        adjL[to].append((start, time))
        
    q = deque([1])
    visited = [-1 for _ in range(N+1)]
    visited[1] = 0
    while q:
        cl = q.popleft()
        for nl, nt in adjL[cl]:
            if visited[nl] == -1:
                visited[nl] = visited[cl] + nt
                q.append(nl)
            else:
                if visited[cl] + nt < visited[nl]:
                    visited[nl] = visited[cl] + nt
                    q.append(nl)
    
    for i in range(1, N+1):
        if visited[i] <= K:
            answer += 1
    
    return answer

풀이 방법

1. 구간을 adjL에 저장한다.
   1. 양방향이므로 가는 방향 오는 방향 둘 다 저장한다.
   2. 저장 할 때 걸리는 시간도 같이 저장한다.
2. 너비 우선 탐색을 진행한다.
   1. -1로 초기한 방문배열을 만든다.
   2. 현재 지점에서 다음 지점으로 갈 때 걸리는 시간을 visited에 저장한다.
   3. 이미 visited에 방문한 기록이 있다면 더 짧은 시간을 저장시킨다.
3. 방문배열에 저장된 시간 중에서 K보다 작거나 같은 시간을 찾아서 answer에 더해준다.

느낀점

• 여기서 더 나아가면 다익스트라가 나오는데 heapq없이 풀 수 있나 모르겠다.
• 자바스크립트로 다익스트라 풀 수 있게 열심히 공부하자.