프로그래머스 - 배달

문제 링크 ▶︎ 프로그래머스 배달

문제 전략

이 문제는 BFS를 통해서 다익스트라 알고리즘으로 푼 문제이다.

노드와 거리 정보를 maps 라는 딕셔너리에 저장하고, visit 은 큰 값으로 채워둔다.
bfs 는 1번 노드부터 queue 에 넣고 빼면서 그 값을 out으로 둔다.
maps 에서 out 노드에서 갈 수 있는 노드를 검색하고, 다음 노드의 visit 값과 out 노드의 visit + dist 를 비교해 최단거리를 구한다.

코드

from collections import deque
def solution(N, road, K):
    answer = 0
    maps = {i:[] for i in range(1,N+1)}
    for arr in road:
        a,b,cost = arr[0],arr[1],arr[2]
        maps[a].append([b,cost])
        maps[b].append([a,cost])
        
    visit = [987654321] * (N+1)
    
    def bfs(visit):
        
        q = deque()
        q.append(1)
        visit[1] = 0
        while q:
            out = q.popleft()
            for lst in maps[out]:
                node, dist = lst[0], lst[1]
                if visit[node] > visit[out] + dist:
                    visit[node] = visit[out] + dist
                    q.append(node)
                    
        return 
    
    bfs(visit)     
    for x in visit[1:]:
        if x <= K:
            answer += 1
            
    return answer

개선 사항

K 보다 작은 노드의 수를 bfs 안에서 구할 수 있을지 고민.