이해

• N개의 마을이 1부터 N까지 번호가 각각 하나씩 부여되어 있고, 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있다.
• 1번 마을에 있는 음식점에서 K시간 이하로 배달이 가능한 마을에서만 주문을 받을 때 음식 주문을 받을 수 있는 마을의 개수를 return하라.

계획

• 1번 마을로부터 모든 마을까지의 최단 경로를 구한다.
• 최단 경로는 다익스트라 알고리즘을 사용하여 구해준다.
• 최단 경로가 K이하인 마을의 개수를 센다.

실행

import heapq

def solution(N, road, K):
    
    graph = [[] for _ in range(N)]
    for a, b, c in road:
        graph[a-1].append((b-1, c))
        graph[b-1].append((a-1, c))
    INF = 1e9
    distances = [INF for _ in range(N)]
    queue = []
    heapq.heappush(queue, (0, 0))
    distances[0] = 0
    
    while queue:
        now, dist = heapq.heappop(queue)
        if dist > distances[now]:
            continue
        for adj in graph[now]:
            cost = dist + adj[1]
            if cost < distances[adj[0]]:
                distances[adj[0]] = cost
                heapq.heappush(queue, (adj[0], cost))
    
    return len([dist for dist in distances if dist <= K])
        

개선

• 딱히 없는 것 같다.

회고

• 최단 경로 유형의 단순한 문제였다. 쉬웠다.
• heqpq 모듈을 오랜만에 사용하다 보니 heapq 모듈에서 제공되는 여러 함수들의 사용법이 잘 기억이 안 났다. 제대로 기억하자!