[백준/C++] #14938 서강그라운드 (Dijkstra)

문제

https://www.acmicpc.net/problem/14938

구상

수색 범위 때문에 낙하지점마다 갈 수 있는 지역들이 다르고, 각 지역들에서 얻을 수 있는 아이템 수가 다르다. 이때, 어떤 지점에 낙하를 해서, 얼마나의 아이템을 얻을 수 있는지 묻는 문제였다. 

 

즉, 한 지점에서 출발을 하면, 최단거리가 수색 범위 이하인 곳들을 추출하고, 그렇게 갈 수 있는 지역들에서 얻을 수 있는 아이템들을 다 더하면 하나의 출발지에서 얻을 수 있는 아이템 수들을 구할 수 있다. 

그래서 결국 이문제의 키 포인트는 최단거리가 수색 범위 이하인 곳들을 추출하는 것이고, 각 길마다 거리가 다르므로, 결국 가중치가 있는 그래프에서 시작 노드로부터 다른 모든 노드까지의 최단 경로를 찾는 데에 사용되는 Dijkstra 알고리즘을 사용했다.

 

이때 우선순위 큐를 사용하여 현재까지의 최단 경로가 가장 짧은 노드를 먼저 처리하여 시간복잡도를 줄였다. 우선순위 큐를 사용하면 확정된 경로를 다시 큐에 들이지 않아 탐색 빈도가 줄어서 시간복잡도가 감소한다. 큐를 사용한다면 최악의 경우 O(V * E)가 되는데, 우선순위 큐를 사용하면 O((V+E)*logV)가 된다.  

 

풀이 + 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
#include<queue>
#define MAX 101
#define INF 987654321
#define endl "\n"
using namespace std;
/*
14938 서강그라운드
*/

int n, m, r; // 지역의 개수, 수색범위, 길의 개수
vector<int> items(101); // 각 지역의 아이템 개수
vector<vector<pair<int, int>>> map(101); // 이렇게 1차원만 초기화. 나머지는 동적 배열에 맡기기
vector<int> total_items(101, 0); // 각 지역에서 얻을 수 있는 아이템 개수

void solution() {
    for (int start = 1; start <= n; start++) { // 각 낙하지점에서 최단 거리 m 안에 있는 아이템들 총합 구하기
        vector<int> min_length(101, INT_MAX);

        priority_queue<pair<int, int>> pq; // 우선선위 큐 사용
        pq.push({ 0, start});
        min_length[start] = 0;

        while (!pq.empty()) { // 최단 거리 m 안에 드는 지역 추출하기
            int len = -pq.top().first;
            int now = pq.top().second;
            pq.pop();

            for (int i = 0; i < map[now].size(); i++) {
                int next = map[now][i].first;
                int update_len = len + map[now][i].second;
                if (update_len < min_length[next] && update_len <= m) {
                    min_length[next] = update_len; // 갱신
                    pq.push({-min_length[next],  next});
                }
            }
        }

        for (int i = 1; i <= n; i++) { // 거리 안에 드는 지역의 아이템들의 총합 구하기
            if (min_length[i] <= m)
                total_items[start] += items[i];
        }

    }

    int res = 0;
    for (int i = 0; i <= n; i++) { // 모든 시작지점에서 구할 수 있는 아이템 총합 중 가장 큰 것 구하기
        res = max(res, total_items[i]);
    }
    cout << res;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> n >> m >> r;
    for (int i = 1; i <= n; i++) { // 1번 도시부터~
        cin >> items[i];
    }

    for (int i = 0; i < r; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        map[a].push_back({ b, c });
        map[b].push_back({ a, c }); // 양방향
    }


    // 로직
    solution();

    return 0;

}