백준 14938번 서강그라운드 (C++)

문제 링크 : https://www.acmicpc.net/problem/14938

14938번: 서강그라운드

문제 요약

 

1. 첫째줄에 지역의 개수 n (1 <= n <= 100), 예은이의 수색범위 m (1<= m <= 15), 길의 개수 r (1<= r <= 100)이 주어집니다.

2. 둘째 줄에는 n개의 숫자가 차례대로  각 구역에 있는 아이템의 수 t (1 ≤ t ≤ 30)가 주어집니다. 

3. 세 번째 줄부터 r+2번째 줄 까지 길 양 끝에 존재하는 지역의 번호 a, b, 그리고 길의 길이 l (1 ≤ l ≤ 15)가 주어진다.

4. 예은이는 1번부터 n번지역에 착륙하여 자신의 수색범위 이하의 지역에있는 아이템들을 가질 수 있습니다

5. 예은기가 가질 수 있는 아이템의 최대개수를 출력하세요.

 

 

핵심 포인트

 

다익스트라로 접근하면 쉽게 풀 수 있습니다.

단, 이 문제는 주어지는 입력값이 크지 않으므로 일반 큐를 통해서도 풀 수 있습니다.

 

또한 시작지점은 랜덤으로 선택할 수 있으므로, 모든 지역마다 최단거리를 구해주면 됩니다.

 

 

문제 풀이

 

먼저 전체 로직을 훑어보겠습니다.

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

int n,m,r,ans = 0;
vector<int> items(101);
vector<pair<int,int>> map[101];
vector<int> dist(101);

void getAnswer(int x){ // 정답 구하기
    int temp = 0;
    for(int i=1; i<=n; i++) if(dist[i]-m<=0) temp += items[i];
    if(ans<temp) ans = temp;
}

void dijkstra(int x){ // 최단거리 구하기
    int pos, npos, ndis;
    queue<int> pq;
    dist[x] = 0;
    pq.push(x);
    while(!pq.empty()){
        pos = pq.front();
        pq.pop();
        for(int i=0; i<map[pos].size(); i++){
            npos = map[pos][i].first;
            ndis = map[pos][i].second;
            if(dist[pos]+ndis<dist[npos]){
                dist[npos] = dist[pos]+ndis;
                pq.push(npos);
            }
        }
    }
    getAnswer(x);
}

void init(){ // 최단거리 초기화
    for(int i=1; i<=n; i++) dist[i] = MAX;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int a,b,c;
    cin >> n >> m >> r;
    for(int i=1; i<=n; i++) cin >> items[i];
    for(int i=0; i<r; i++){
        cin >> a >> b >> c;
        map[a].push_back({b,c});
        map[b].push_back({a,c});
    }
    for(int i=1; i<=n; i++){
        init();
        dijkstra(i);
    }
    cout << ans << "\n";
    return 0;
}

다익스트라로도 풀 수 있고 일반 큐로도 풀 수 있습니다. 위 해설은 일반 큐로 접근하여 문제를 해결하였습니다.

 

 

(1) 입력값으로 주어지는 값들을 저장합니다.

    int a,b,c;
    cin >> n >> m >> r;
    for(int i=1; i<=n; i++) cin >> items[i];
    for(int i=0; i<r; i++){
        cin >> a >> b >> c;
        map[a].push_back({b,c});
        map[b].push_back({a,c});
    }

 

(2) 1번부터 N번까지 최단거리를 초기화 해준뒤, 다익스트라를 통해 최단거리를 다시 구해줍니다.

    for(int i=1; i<=n; i++){
        init();
        dijkstra(i);
    }

최단거리를 초기화하는 로직은 단순하므로 설명을 생략합니다.

 

(3) 현재 지점 (x)부터 각 지역마다의 최단거리를 구합니다.

void dijkstra(int x){
    int pos, npos, ndis;
    queue<int> pq;
    dist[x] = 0;
    pq.push(x);
    while(!pq.empty()){
        pos = pq.front();
        pq.pop();
        for(int i=0; i<map[pos].size(); i++){
            npos = map[pos][i].first;
            ndis = map[pos][i].second;
            if(dist[pos]+ndis<dist[npos]){ // 1
                dist[npos] = dist[pos]+ndis;
                pq.push(npos);
            }
        }
    }
    getAnswer(x); // 2
}

위 코드에서 핵심 설명만 요약하면 다음과 같습니다.

(1) 현재 큐의 최상단에 삽입된 위치에서 다음 위치로 갈때, 현재 위치에 누적된 거리비용 + 다음 위치로 가기 위한 거리비용 < 다음 위치에 누적된 거리비용일 경우, 다음 위치에 누적된 거리비용을 갱신해주고 큐에다 다음위치를 삽입하면 됩니다.

(2) while문을 빠져나오고 현재 위치에서 수색 가능한 범위의 아이템의 합을 구하기 위해 getAnswer함수를 사용합니다. 이때 매개변수로 시작위치 x를 받습니다.

 

(3) 정답을 구하는 getAnswer함수입니다.

void getAnswer(int x){
    int temp = 0;
    for(int i=1; i<=n; i++) if(dist[i]-m<=0) temp += items[i];
    if(ans<temp) ans = temp;
}

1번부터 n번까지 for문을 돌려 갈 수 있는 범위라면 해당 위치의 아이템을 temp에 더해주면 됩니다.

마지막으로 ans와 temp중 더 큰 값을 ans로 갱신합니다.

 

(4) 모든 과정을 마치고 main함수에서 ans변수의 값을 출력합니다.