[프로그래머스][C++] 배달

배달

문제 링크

배달

분석

마을은 N개가 있고, 마을간 도로를 통해 양방향으로 이동할 수 있습니다.

항상 1번 마을에서 출발합니다.

배달이 가능한 최대 시간이 K일 때 1번 마을에서 K이하의 시간 내에 도착할 수 있는 마을의 개수를 구해야합니다.

마을은 양방향으로 가중치가 존재하며, 순회하지 않는 그래프입니다.
해당 그래프를 순회해야하는 문제입니다.

특정 정점에서 다른 정점까지 가는데 최단 경로를 구하는 알고리즘은 크게 3가지가 있습니다.

1. 다익스트라 알고리즘
2. 벨만포드 알고리즘
3. 플로이드 워샬 알고리즘

해당 문제에서는 1번 정점에서 나머지 정점들에 대한 최단경로만 구하면 되기 때문에 다익스트라 알고리즘을 사용합니다.

풀이

#include <vector>
#include <queue>
#include <limits>

using namespace std;

// 다익스트라 알고리즘
// 특정 정점에서 방문 할 수 있는 모든 노드들의 최단 경로를 구한다.
vector<int> dijkstra(int N, vector<vector<pair<int, int>>>& graph, int start)
{
    vector<int> dist(N + 1, numeric_limits<int>::max());  // 각 마을까지의 최단거리를 저장
    
    // 최솟값을 먼저 꺼낼 수 있는 우선순위 큐
    // pair<int, int>는 큐에 저장될 요소의 자료형으로 비용과 노드 번호를 의미
    // vector<pair<int, int>>는 연결된 마을과 이동 시간을 의미
    // 최솟값을 먼저 꺼내야 하므로, greater<>를 사용
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

    // 1번 마을의 최단 거리는 0
    dist[start] = 0;
    // 1번 마을에서부터 시작
    pq.push({0, start});

    while (!pq.empty())
    {
        int cost = pq.top().first;  // 현재 노드까지의 비용
        int node = pq.top().second; // 현재 노드의 번호
        pq.pop();

        // 이미 더 짧은 경로가 존재하면 스킵
        if (cost > dist[node])
        {
            continue;
        }

        // 현재 노드에 연결된 모든 노드 탐색
        for (auto& [next, nextCost] : graph[node])
        {
            // 다음 노드까지의 새로운 거리 계산
            int newCost = cost + nextCost;

            // 더 짧은 거리를 발견한다면 값을 갱신
            if (newCost < dist[next])
            {
                dist[next] = newCost;
                pq.push({newCost, next});
            }
        }
    }
    
    return dist;
}

int solution(int N, vector<vector<int> > road, int K) {
    
    int answer = 0;
    
    // 가중치를 가지는 양방향 그래프
    vector<vector<pair<int, int>>> graph(N + 1);
    
    // 그래프의 정보 저장
    for(auto& e : road)
    {
        int a = e[0];
        int b = e[1];
        int weight = e[2];
        
        graph[a].push_back({b, weight});
        graph[b].push_back({a, weight});
    }

    // 방문 할 수 있는 마을 목록을 가져온다.
    vector<int> dist = dijkstra(N, graph, 1);

    // 방문 할 수 있는 마을 목록 중에서 K보다 작은 값으로 배달이 가능한 마을을 확인한다.
    for (int i = 1; i <= N; ++i)
    {
        if (dist[i] <= K)
        {
            ++answer;
        }
    }

    return answer;
}

성능 요약

시간 복잡도는 $O(r \ log \ n)$입니다.

• 그래프의 정보를 저장하는 반복문 $O(r)$
  • r은 road의 크기
• 다익스트라 알고리즘 $O((n + r) \ log \ n)$
  • n은 정점의 개수
• 배달이 가능한 마을을 확인하는 반복문 $O(n)$
• $O(r \ log \ n) + O(n) + O(r)$

공간 복잡도는 $O(n + r)$입니다.

• 가중치를 가지는 양방향 그래프 vector<vector<pair<int, int>>> graph $O(n + r)$
• 거리를 저장하는 배열 vector<int> dist $O(n)$
• 우선순위 큐 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; $O(n)$
• $O(n + r)$ + $O(n)$ + $O(n)$

테스트 1 〉 통과 (0.01ms, 4.2MB)
테스트 2 〉 통과 (0.01ms, 4.2MB)
테스트 3 〉 통과 (0.01ms, 4.14MB)
테스트 4 〉 통과 (0.01ms, 4.14MB)
테스트 5 〉 통과 (0.01ms, 4.2MB)
테스트 6 〉 통과 (0.01ms, 4.13MB)
테스트 7 〉 통과 (0.01ms, 4.14MB)
테스트 8 〉 통과 (0.01ms, 4.2MB)
테스트 9 〉 통과 (0.01ms, 4.21MB)
테스트 10 〉 통과 (0.01ms, 4.2MB)
테스트 11 〉 통과 (0.02ms, 4.2MB)
테스트 12 〉 통과 (0.02ms, 4.2MB)
테스트 13 〉 통과 (0.02ms, 3.67MB)
테스트 14 〉 통과 (0.12ms, 3.87MB)
테스트 15 〉 통과 (0.18ms, 3.98MB)
테스트 16 〉 통과 (0.01ms, 4.21MB)
테스트 17 〉 통과 (0.02ms, 3.59MB)
테스트 18 〉 통과 (0.06ms, 4.14MB)
테스트 19 〉 통과 (0.16ms, 3.91MB)
테스트 20 〉 통과 (0.06ms, 3.64MB)
테스트 21 〉 통과 (0.19ms, 4.13MB)
테스트 22 〉 통과 (0.07ms, 4.21MB)
테스트 23 〉 통과 (0.18ms, 4.05MB)
테스트 24 〉 통과 (0.13ms, 3.88MB)
테스트 25 〉 통과 (0.21ms, 4.15MB)
테스트 26 〉 통과 (0.34ms, 4.13MB)
테스트 27 〉 통과 (0.22ms, 4.14MB)
테스트 28 〉 통과 (0.26ms, 4.14MB)
테스트 29 〉 통과 (0.21ms, 4.11MB)
테스트 30 〉 통과 (0.24ms, 4.17MB)
테스트 31 〉 통과 (0.02ms, 4.02MB)
테스트 32 〉 통과 (0.03ms, 4.16MB)