(C++) - 백준(BOJ) 14938 : 서강그라운드

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

14938번: 서강그라운드

dijkstram로 해결한 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

 지역 개수 n, 수색 범위 m, i번 지역까지의 거리를 저장할 일차원 배열 dist, item정보를 입력받을 일차원 배열 items, 답을 출력할 ans, graph정보를 입력할 vector형 변수 graph를 선언해줍니다. 이후 적절히 입력해줍니다.

 

📔 풀이과정

시작점으로부터 최단거리로 어떤 지역으로 갔을 때 m이하의 거리라면 그 지역의 item을 얻을 수 있습니다.

 

 1. 시작 낙하지역을 정하고 각 지역까지의 최단거리를 구한 뒤 m이하의 거리인 수색범위 안에 위치한 지역들의 아이템들을 모두 더한 값을 반환하는 dijkstra함수를 수행합니다. 각 거리를 구한뒤 dist배열을 확인해 start번 지역에서 시작해 i번째 지역까지의 최단거리가 m이하라면 임시변수 totalItem에 더해줍니다. 이 후 totalItem을 반환해줍니다.

 

 2. dijkstra함수의 결과값의 최댓값을 ans에 저장합니다.

 

📔 정답출력

ans를 출력해줍니다.

---

📕 Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
using pii = pair<int,int>;
struct Edge {int v, w; };
int n, m, r, dist[101], items[101], ans;
vector <Edge> graph[101];

int dijkstra(int start){
    int totalItem = 0;
    priority_queue <pii, vector<pii>, greater<pii>> pq;
    dist[start] = 0;
    pq.push({0, start});
    while(!pq.empty()){
        int cur = pq.top().second;
        int cost = pq.top().first;
        pq.pop();
        if(dist[cur] < cost ) continue;
        for(auto g : graph[cur]){
            int next = g.v;
            int nextCost = g.w;
            if(cost + nextCost < dist[next]) {
                dist[next] = cost + nextCost;
                pq.push({dist[next], next});
            }
        }
    }
    for(int i = 1; i <= n; i++)
        if(dist[i] <= m)
            totalItem += items[i];
    return totalItem;
}

int main(){
    cin >> n >> m >> r;
    for(int i = 1; i <= n; i++) cin >> items[i];
    while(r--) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }
    for(int i = 1; i <= n; i++) {
        memset(dist, INF, sizeof(dist));
        ans = max(ans, dijkstra(i));
    }
    cout << ans;
}