[BAEKJOON] 2463번 비용

https://www.acmicpc.net/problem/2463

문제조건

1. 가중치그래프가 존재한다.
2. 서로다른 정점 u, v에 대해서 경로가 있다면 경로가 없을때까지 최소 가중치 간선을 제거한다. 
3. u < v 인 모든 두 정점에 대해 제거되는 가중치들의 총합을 구하시오. 

접근방법

 

딱봐도 MST(최소비용신장트리)와 정말 유사하게 동작하는 문제였다. 그리디한 접근법인 Prim, Kruskal 알고리즘을 떠올렸는데, 이 알고리즘의 핵심은 서로소 분리 집합으로 초기에 모든 노드(정점)을 각각 독립적인 집합으로 초기화 시킨후, 집합이 하나가 될때까지 최소비용인 간선들을 더해가는 것이다. Kruskal 알고리즘과 이 문제의 차이점은, 최대 가중치를 가진 간선부터 그래프에 추가한다는 점이다.

 

1. 간선의 가중치를 내림차순으로 정렬한다.
2. 임의의 간선부터 시작해서 정점이 속해있는 집합이 서로다른 경우에만 서로 경로가 생기기 직전(같은 집합이 되기)까지의 집합 원소의 개수를 곱해준다.(u < v라고 했으므로 중복으로 더해줄필요는 없다.)
   1. 곱해주는 이유는 서로다른 두집합을 분리했다고해서 두 정점만 경로가 생기는 것이아니라, 각각 원소에 대한 경로가 모두 생기는 것이기때문에 모든 조합의 수를 알아야하기 때문이다.
3. 총 가중치에서 현재 이어진 간선의 가중치를 뺀값을 2. 에 곱해준다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 100001
#define MOD 1000000000
using namespace std;

int n, m, u, v;
vector<pair<pair<int, int>, int >> edge;
long long parent[MAX], slice[MAX];
long long res, sum;

bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
	return a.second > b.second;
}

int find(int num) {
	if (num == parent[num]) return num;
	return parent[num] = find(parent[num]);
}

void merge(int n1, int n2) {
	parent[n2] = n1;
	slice[n1] += slice[n2];
	slice[n2] = 1;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y, w;
		cin >> x >> y >> w;
		edge.push_back({ { x, y }, w });
		sum += w;
	}
	// 서로소 분리 집합 초기화
	for (int i = 1; i <= n; i++) {
		parent[i] = i;
		slice[i] = 1;
	}
	// 가중치기준으로 내림차순 정렬
	sort(edge.begin(), edge.end(), cmp);
	for (int i = 0; i < edge.size(); i++) {
		int n1 = find(edge[i].first.first);
		int n2 = find(edge[i].first.second);
		int weight = edge[i].second;
		if (n1 != n2) {
			res += slice[n1] * slice[n2] % MOD * sum % MOD;
			res %= MOD;
			merge(n1, n2);
		}
		sum -= weight;
	}
	cout << res;

}

 

---

이때까지 내가 알아온 알고리즘과 비슷하다면 그 알고리즘을 활용해서 어떻게 풀수있을까라는 생각을 해볼수 있었고, 역시 뭔가 잘 안풀린다면 거꾸로 생각해서 응용하는것도 방법인거같다.