백준 2463번 비용

문제 링크입니다: https://www.acmicpc.net/problem/2463

발상의 전환이 필요했던 유니온 파인드(Union Find) 문제였습니다.

같은 학교 학우인 degurii(http://degurii.tistory.com/)의 도움으로 풀 수 있었습니다.

알고리즘은 아래와 같습니다.

1. M개의 입력을 받은 뒤 비용을 기준으로 내림차순 정렬을 해줍니다.

2. 가중치가 큰 간선부터 이어가면서 간선끼리 이어진 노드들은 같은 집합 연결되어있지 않은 노드들은 다른 집합으로 간주하여 답을 구합니다.

3. 즉, 서로 다른 집합이였던 노드들이 같은 집합으로 되기 직전에 계산을 하여 Cost(num1, num2)의 값을 구합니다.

3번의 부연 설명으로 예시로 나온 그림을 첨부하였습니다.

i) 가중치가 제일 큰 3-6과 두 번째로 큰 1-2가 이어져있는 상황에서 2-6을 잇기 직전 상황입니다.

ii) 현재 상황에서는 Cost(2, 3), Cost(2, 6), Cost(1, 3), Cost(1, 6)의 합을 구할 수 있습니다.

iii) ii)의 결과는 (num1의 집합 크기 * num2의 집합 크기) * (전체 간선 가중치 합 - 현재 이어진 간선 가중치 합)입니다.

4. 따라서, 내림차순 정렬한 간선들을 하나하나 연결하면서 연결한 정점들이 서로 다른 집합이였다면 3.(iii)의 공식을 통해 Cost 합을 구합니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

const int MOD = 1000000000;

const int MAX = 100000 + 1;

 

int N, M;

int parent[MAX];

vector < pair<pair<int, int>, int>> edge; //num1, num2, cost

long long setSize[MAX], total;

 

//집합의 루트를 찾는다

int find(int num)

{

        if (num == parent[num])

                 return num;

 

        return parent[num] = find(parent[num]);

}

 

//num1의 집합에 num2 집합을 합친다

void merge(int num1, int num2)

{

        parent[num2] = num1;

        setSize[num1] += setSize[num2];

        setSize[num2] = 1;

}

 

bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b)

{

        if (a.second > b.second)

                 return true;

        return false;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> M;

 

        for (int i = 0; i <= N; i++)

        {

                 parent[i] = i;

                 setSize[i] = 1;

        }

        for (int i = 0; i < M; i++)

        {

                 int num1, num2, cost;

                 cin >> num1 >> num2 >> cost;

 

                 edge.push_back({ {num1, num2}, cost });

                 total += cost;

        }

        sort(edge.begin(), edge.end(), cmp); //가중치 내림차순 정렬

       

        long long result = 0;

        for (int i = 0; i < edge.size(); i++)

        {

                 int parentNum1 = find(edge[i].first.first);

                 int parentNum2 = find(edge[i].first.second);

                 int cost = edge[i].second;

                

                 //둘이 같은 집합이 아닌 경우

                 if (parentNum1 != parentNum2)

                 {

                         result += (((setSize[parentNum1] * setSize[parentNum2]) % MOD) * total) % MOD;

                         result %= MOD;

                         //같은 집합으로 합친다

                         merge(parentNum1, parentNum2);

                 }

                 total -= cost;

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~