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

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

14938번: 서강그라운드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M, R, result;
vector<pii>v[101];
int arr[101];
int dist[101];
priority_queue<pii,vector<pii>,greater<pii>> pq;

void dijkstra(int s)
{
    for(int i=0; i<N; i++) dist[i]=MAX;
    dist[s] = 0;
    pq.push({0, s});

    while(!pq.empty()) //거리값 저장
    {
        auto[cost, cur] = pq.top();
        pq.pop();

        for(int i=0; i<v[cur].size(); i++)
        {
            auto[next, ncost] = v[cur][i];
            if(cost + ncost >= dist[next]) continue;
            dist[next] = cost + ncost;
            pq.push({dist[next], next});
        }
    }

    int sum = 0;
    for(int i=0; i<N; i++) //가능한 거리에 대한 최대 값 저장
    {
        if(dist[i] > M) continue;    
        sum += arr[i];
    }
    result = max(result, sum);

}
int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> M >> R;

    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }
    
    for(int i=0; i<R; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v[a-1].push_back({b-1, c}); //양방향 통행
        v[b-1].push_back({a-1, c});
    }

    for(int i=0; i<N; i++)
    {
        dijkstra(i); //모든 정점에서 탐색
    }

    cout << result;
    
    return 0;
}

플로이드-워셜 또는 데이크스트라로 풀리는 문제이다.

나는 데이크스트라가더 익숙해서 데이크스트라로 풀었다.

 

기본 데이크스트라에 추가적으로 거리에 대한 최대값을 저장해야 한다.

따라서 모든 정점에 대하여 데이크스트라를 돌려주고, 각 정점을 기준으로 거리를 구했을 때 가능한 거리인 M까지 얻을 수 있는 아이템의 갯수를 더해준다.

이렇게 구한 아이템의 갯수가 최대일 때를 따로 저장하여 출력해주면 된다.

 

해당 문제를 풀 때 번호가 0번이 아닌 1번부터 시작한다는 것을 고려하지 않아서 여러번 틀렸다.

별 생각없이 i=0부터 해서 아이템 배열을 채워나갔는데, 간선에 대한 값을 저장할 때는 0부터가 아니라 1부터를 기준으로 입력받는다.

따라서 간선인 a, b를 시작값인 0에 맞춰서 1씩 빼주거나,  앞에서 입력받고 나머지 탐색에 대해서도 i=1부터 시작하도록 해주어야 한다.

 

그리고 모든 정점에 대해서 데이크스트라를 돌려주는 것이기 때문에 매 탐색마다 초기화해주는 것도 잊으면 안된다.