프로그래머스 등급2 - 배달

배달 문제 바로 가기

풀이 날짜: 2026-05-01

baekjoon 알고리즘 문제 풀이

풀이 코드


import heapq

def solution(n, road, k):
    INF = int(1e9)
    
    distance = [INF] * (n+1)
    
    graph = [[] for _ in range(n+1)]
    for i in range(len(road)):
        a = road[i][0]
        b = road[i][1]
        c = road[i][2]
        
        graph[a].append((b,c))
        graph[b].append((a, c))
    
    def dijkstra(start):
        q = []
        
        heapq.heappush(q,(0,start))
        distance[start] = 0
        
        while q:
            dist, now = heapq.heappop(q)
            
            if distance[now] < dist:
                continue
            for i in graph[now]:
                cost = dist + i[1]
                if cost < distance[i[0]]:
                    distance[i[0]] = cost
                    heapq.heappush(q,(cost,i[0]))
    dijkstra(1)
    
    answer = 0
    for i in distance:
        if i <= k:
            answer += 1
    return answer

문제 핵심

1번 마을에서 출발하여, K 시간 이내에 도달할 수 있는 마을의 개수를 구하는 문제이다. 각 마을은 도로로 연결되어 있으며, 도로마다 이동 시간이 존재한다. 즉, 최단 거리(시간)을 구하는 문제이므로 다익스트라 알고리즘을 사용했다.

접근 방법 (아이디어)

이 문제는 1번 마을에서 시작하여 모든 마을까지의 최소 이동 시간을 구한 뒤, 그 중에서 K 이하인 마을 개수를 세면 된다.

이를 위해 다음과 같은 순서로 해결한다.

인접 리스트 (그래프)를 만든다.
다익스트라로 최단 거리를 계산한다.
거리 배열에서 k이하 개수를 카운트 한다.

그래프 구성

문제에서 중요한 포인트는 도로가 양방향이라는 것이다. 따라서 아래와 같이 그래프를 구성해야 했다.

graph[a].append((b, c))
graph[b].append((a, c))

다익스트라 알고리즘 구현

다익스트라는 우선순위 큐(heapq)를 이용해서 구현한다. 핵심 흐름은 다음과 같다. 1) 시작 노드를 1로 설정한다. 2) 거리 배열은 INF로 초기화한다. 3) 시작점은 거리 0이다. 4) 가장 짧은 거리부터 탐색한다. 5) 더 짧은 경로를 발견하면 갱신한다.