배달

배달

사용 언어: C++

문제 요약

• 한 마을에 N개의 마을(지점)이 있고, 도로(양방향, 이동 시간)가 존재합니다.
• 각 마을에서 배달을 하려고 할 때, 제한 시간 K 안에 도달 가능한 마을 수를 구하는 문제입니다.
• 핵심: 최단 거리 계산 후, 거리 ≤ K인 마을 수를 세기.

다익스트라 설명

시작 지점인 첫 번째 노드에서 도달 가능한 모든 마을을 구하려는 문제이므로, 다익스트라로 풀어야한다.

다익스트라는 다음과 같이 간단하게 요약할 수 있다.

다익스트라 요약

1. 단일 출발점 최단 거리 알고리즘

2. 가중치가 양수인 경우 사용 가능 (음수는 벨만포드)

3. 우선순위 큐 활용 -> 최소 거리 노드부터 처리

다익스트라 구현 흐름

1. 거리 배열 초기화

vector<int> dist(N+1, INF); // INF or 1e9 같은 큰 숫자
dist[start] = 0;

2. 우선순위 큐 초기화

priority_queue<pair<int,int>, vector<pair<int, int>>, greater<pair<int,int>>> pq;
pq.push({0, start}); // {거리, 노드} -> 최소 거리 순으로 정렬하기 위해 거리부터 넣음.

3. 최소 거리 노드 꺼내기

while(!pq.empty())
{
    auto [curDist, curNode] = pq.top(); pq.pop();
    if(curDist > dist[curNode]) continue; // 같은 노드 내 중복 처리 (더 긴 길 있을 경우)
    
    for(auto [nextNode, cost] : adj[curNode])
    {
        // 기존 값보다 새로운 경로의 길이 값이 작을 때 갱신 및 push
        if(dist[nextNode] > curDist + cost)
        {
            dist[nextNode] = curDist + cost;
            pq.push({dist[nextNode], nextNode});
        }
    }
}

풀이

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

const int MAX = 10001;

int solution(int N, vector<vector<int> > road, int K) 
{
    int answer = 0;

    vector<vector<pair<int,int>>> arr(N+1);
    
    for(vector<int> v : road)
    {
        arr[v[0]].push_back({v[1], v[2]});
        arr[v[1]].push_back({v[0], v[2]});
    }
    
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    vector<int> dist(N+1, 1e9);
    dist[1] = 0;
    pq.push({dist[1], 1}); // 거리, 시작 지점
    
    while(!pq.empty())
    {
        int curDist = pq.top().first; 
        int curNode = pq.top().second;
        pq.pop();
        
        if(curDist > dist[curNode]) continue; // 중복 간선 처리 (짧은 거만 따짐)
        
        for(auto [nextNode, cost] : arr[curNode])
        {
            if(dist[nextNode] > curDist + cost)
            {
                dist[nextNode] = curDist + cost;
                pq.push({dist[nextNode], nextNode});
            }
        }
    }
    
    for(int cost : dist)
    {
        if(cost <= K) answer++;
    }

    return answer;
}