[프로그래머스 12978] 배달

• 출처: 프로그래머스 12978
• 분류: 그래프 · Lv.2

문제

N개 마을과 양방향 도로가 주어진다. 1번 마을에서 각 마을까지 최단 시간을 구해, K 시간 이하로 배달 가능한 마을의 수를 반환한다. 두 마을 사이 도로가 여러 개 있을 수 있다.

핵심

가중치 있는 그래프에서 단일 출발점 최단 경로 → 다익스트라. BFS는 가중치가 동일할 때만 쓸 수 있다.

풀이

#include <vector>
#include <queue>
using namespace std;

struct Node {
    int id, cost;
    bool operator>(const Node& o) const { return cost > o.cost; }
};

int solution(int N, vector<vector<int>> road, int K) {
    vector<vector<pair<int,int>>> adj(N + 1);
    for (auto& r : road) {
        adj[r[0]].push_back({r[1], r[2]});
        adj[r[1]].push_back({r[0], r[2]});
    }

    vector<int> dist(N + 1, 1e9);
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    dist[1] = 0;
    pq.push({1, 0});

    while (!pq.empty()) {
        auto [u, d] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;

        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({v, dist[v]});
            }
        }
    }

    int answer = 0;
    for (int i = 1; i <= N; i++) {
        if (dist[i] <= K) answer++;
    }
    return answer;
}

메모

• BFS가 아닌 다익스트라인 이유
  • 도로마다 가중치(시간)가 다르다. BFS는 모든 간선의 가중치가 동일할 때만 최단 경로를 보장한다
  • 게임 맵 최단거리는 칸 이동 비용이 모두 1이라 BFS로 풀었다. 이 문제는 가중치가 다르므로 다익스트라를 쓴다
• d > dist[u] 체크
  • 같은 노드가 더 짧은 경로로 갱신되어 pq에 다시 들어갈 수 있다. 이전에 넣은 (더 긴) 항목이 나중에 pop될 때, 이미 더 짧은 거리가 확정된 상태이므로 건너뛴다
  • 이 체크 없이도 정답은 나오지만, 불필요한 간선 탐색을 막아 성능이 향상된다
• 중복 도로 처리
  • 두 마을 사이 도로가 여러 개일 수 있다. 인접 리스트에 모두 넣으면 다익스트라가 자동으로 최소 비용만 채택한다. 별도 처리 불필요
• priority_queue 설정
  • greater<Node>로 min-heap을 만든다. operator>를 정의하면 greater가 이를 사용한다
  • 기본 priority_queue는 max-heap이므로, 다익스트라에서는 반드시 min-heap으로 바꿔야 한다

복잡도

풀이	시간	공간
Dijkstra	O((V+E) log V)	O(V+E)