[BOJ 2463 // C++] 비용

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

 

이번에 볼 문제는 백준 2463번 문제인 비용이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/2463

2463번: 비용

이 문제를 풀기 위해 잠시 생각을 해보자.

 

어떤 에지가 지워졌을 때 그 두 에지의 양 끝을 잇는 점 사이에 경로가 존재하지 않는다면, 각 에지가 속해있는 component에서 각각 하나씩 뽑은 노드 사이의 경로도 그 순간 전부 사라지게 될 것이다. 따라서, 이러한 에지가 사라질 경우, 이때까지 지운 에지들의 가중치의 합을 답에 두 component의 크기를 곱한 횟수만큼 더하는 것으로 답을 구할 수 있을 것이다.

 

별개인 집합을 하나로 합치는 Disjoint Set 자료구조를 이용하여 문제에서의 에지가 지워지는 과정을 거꾸로 거슬러올라가면서(에지를 그으며 component를 하나로 합치면서) 위 생각을 이용하면 이 문제를 쉽게 해결할 수 있다.

 

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

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

long long ans = 0;
long long sum = 0;

int arr[100001];
long long cnt[100001];
priority_queue<pair<long long, pair<int, int>>> pq;

int findf(int x) {
    if (x == arr[x]) return x;
    else return arr[x] = findf(arr[x]);
}

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

    int N, M; cin >> N >> M;

    for (int i = 1;i <= N;i++) {
        arr[i] = i;
        cnt[i] = 1;
    }

    for (int i = 0;i < M;i++) {
        int x, y; long long w; cin >> x >> y >> w;
        pq.push({ w,{x,y} });
        sum += w;
    }

    while (!pq.empty()) {
        int x = findf(pq.top().second.first), y = findf(pq.top().second.second);
        long long w = pq.top().first;
        pq.pop();

        if (x != y) {
            ans += cnt[x] * cnt[y] * sum;
            ans %= 1000000000;
            arr[y] = x;
            cnt[x] += cnt[y];
        }
        
        sum -= w;
    }

    cout << ans;
}