[BOJ 14938 // C++] 서강그라운드

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 14938번 문제인 서강그라운드이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/14938

14938번: 서강그라운드

BFS나 Floyd-Warshall로도 충분히 해결 가능하겠지만, 그래프의 크기가 작고, 탐색이 필요한 거리가 짧으므로 다익스트라(dijkstra) 알고리즘으로 풀어보았다.

 

이 문제를 다익스트라 알고리즘으로 해결하려면 다음과 같이 풀면 된다.

1) 각 노드에서 다익스트라 알고리즘을 실행한다. 이때, 어떤 노드의 가장 짧은 거리가 M을 넘어서면 그 이상의 그래프 정보는 필요없으므로 알고리즘을 중단한다.

2) 각 노드까지의 거리가 M 이하인 노드에 대응되는 아이템의 개수를 더한 합을 구한다.

3) 2에서 구한 합들 중 최댓값을 구한다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
using std::cin;
using std::cout;
using std::vector;
using std::priority_queue;
using std::pair;

int items[101];
int dist[101];
bool done[101];
vector<pair<int, int>> G[101];

int main()
{
    int N, M, R;
    cin >> N >> M >> R;
    for (int i = 1;i <= N;i++) {
        int x; cin >> x;
        items[i] = x;
    }
    for (int i = 0;i < R;i++) {
        int a, b, w;
        cin >> a >> b >> w;
        G[a].push_back({ b,w });
        G[b].push_back({ a,w });
    }
    int ans = 0;
    for (int i = 1;i <= N;i++) { // 각각의 노드에 대하여 dijkstra를 이용
        priority_queue<pair<int, int>> pq;
        for (int j = 1;j <= N;j++) {
            dist[j] = 2222;
            done[j] = false;
        }
        dist[i] = 0;
        pq.push({ 0,i });
        while (!pq.empty()) {
            int current = pq.top().second; pq.pop();
            if (done[current]) continue;
            else if (dist[current] > M) break; // M을 넘어서는 거리가 등장하면 탐색 중단
            done[current] = true;
            for (auto following : G[current]) {
                int fnode = following.first;
                int fweight = following.second;
                if (dist[fnode] > dist[current] + fweight) {
                    dist[fnode] = dist[current] + fweight;
                    pq.push({ -dist[fnode],fnode });
                }
            }
        }
        int s = 0;
        for (int j = 1;j <= N;j++) s += (dist[j] <= M) ? items[j] : 0; // 거리가 M 이하인 점에 대해서만
        if (s > ans) ans = s;
    }
    cout << ans;

    return 0;
}