[BOJ/Gold 1] 백준 17398 통신망 분할(C++)

문제 링크

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

17398번: 통신망 분할

 

문제

BOJ의 인기스타, 방송인 권욱제는 통신 회사에 취업했다. 현재 이 통신 회사는 너무나 큰 통신망을 한 지사에서 관리하느라 큰 비용을 지불하고 있었다. 그래서 회사는 최근 IT의 트렌드 중 하나인 '탈중앙화'에 편승하여, 통신망을 분할하도록 결정했다. 그래서 욱제한테 통신망을 분할 할때 발생하는 비용을 분석하도록 지시했다.

현재 회사 망에는 1번부터 N번까지 총 N개의 통신 탑이 존재하며, 통신탑 간의 연결이 M개 존재한다. 이때 회사에서는 총 Q번 통신탑 간의 연결을 제거함으로써 하나의 통신망을 여러 개의 통신망으로 분리하려고 한다. 통신망이란, 통신탑의 연결을 통해 도달 가능한 통신탑들의 집합이다. 통신탑 간의 연결 관계를 제거할 때 드는 비용은 제거한 후 통신망이 두 개로 나누어진다면 나눠진 두 개의 통신망에 속한 통신탑들의 갯수의 곱이 되며, 나누어지지 않을 경우 0이다.

<그림 1>

그림 1을 예시로 할때, 연결 (3, 4)를 제거하면 {1, 2, 3}, {4, 5, 6}으로 분할 되며, 이때 발생하는 비용은 3 × 3 = 9가 된다. 대신 연결 (2, 3)을 제거하면, 망이 나눠지지 않았기에 비용은 0이 된다.

욱제는 회사의 요청에 따라 Q번의 제거를 통해 나오는 비용의 합을 구해야 한다. 하지만 욱제는 회사의 통신망을 이용해 방송하기 바쁘기 때문에 우리가 도와주자.

입력

첫 번째 줄에는 통신탑의 개수인 자연수 N, 통신탑 사이의 연결의 개수인 자연수 M, 통신망 연결 분할 횟수인 자연수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000, 1 ≤ Q ≤ M)

두 번째 줄부터 M개의 줄에 걸쳐 두 개의 자연수 X, Y가 공백으로 구분되어 주어진다. 이는 X 통신탑과 Y 통신탑 사이에 연결이 있음을 뜻한다. (1 ≤ X, Y ≤ N, X ≠ Y)

중복된 연결은 주어지지 않으며, 모든 통신탑은 처음엔 하나의 통신망에 속한다. 조건에 의해 자기 자신과 연결이 있는 통신탑은 없다.

그 다음 줄부터 Q개의 줄에 걸쳐 제거될 연결의 번호인 자연수 A가 주어진다. 이는 A번째로 입력된 (X, Y)의 연결이 제거되었음을 의미한다. (1 ≤ A ≤ M)

이미 제거된 연결은 다시 제거되지 않으며, 제거는 입력 순서대로 진행된다.

출력

첫 번째 줄에 Q개의 연결을 순서대로 제거하는데 드는 비용의 합을 출력한다.

예제 입력 1

4 4 3
1 2
2 3
3 4
1 4
4
2
3

예제 출력 1

5

첫 번째로 제거되는 연결은 (1, 4)로, 통신망 {1, 2, 3, 4}가 분리되지 않아 비용이 0이다.

두 번째로 제거되는 연결은 (2, 3)으로, 통신망 {1, 2, 3, 4}가 {1, 2}와 {3, 4}로 분리되어 비용이 2 × 2 = 4이다.

세 번째로 제거되는 연결은 (3, 4)로, 통신망 {3, 4}가 {3}과 {4}로 분리되어 비용이 1 × 1 = 1이다.

결과적으로 총 비용은 0 + 4 + 1 = 5이다.

알고리즘 분류

• 자료 구조
• 유니온 파인드

풀이

역순으로 하는 것이 맞다고 생각했으나 딱 거기까지만 생각나서 힌트를 찾아보았다.

우선 모든 통신탑은 처음에는 하나의 통신망에 속한다고 하였기 때문에 모든 통신탑의 Parent가 같다. 따라서 처음에 끊을 연결을 제외한 모든 연결만을 유니온 파인드를 사용하여 묶어 주고, 끊을 연결들을 역순으로 탐색하여(여기서 본인은 스택을 사용함) X, Y를 유니온 파인드로 묶어 준다. 이 때 X, Y의 Parent가 같았다면 비용은 0이고, Parent가 달랐다면 X가 속한 통신망의 통신탑의 개수와 Y가 속한 통신망의 통신탑의 개수의 곱이 바로 연결을 끊을 비용이 된다. 이렇게 되면 언젠가는 통신탑들이 전부 하나의 통신망으로 연결될 것이고, 그 이후부터는 연결을 끊을 비용이 전부 0이 된다.

Q개의 연결들을 끊을 때 사용할 비용의 합을 구해주면 된다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100001
#define LL long long
#define INF 1e9

using namespace std;
int N, M, Q;
int Parent[MAX];
LL Cnt[MAX];
bool visited[MAX];
stack<int> S;
vector<pair<int, int> > Line;
LL answer = 0;

void Init() {
	for (int i = 1; i <= N; i++) {
		Parent[i] = i;
		Cnt[i] = 1;
	}
}

int Find(int X) {
	if (Parent[X] == X) {
		return X;
	}
	return Parent[X] = Find(Parent[X]);
}

void Union(int X, int Y) {
	int PX = Find(X);
	int PY = Find(Y);
	if (PX < PY) {
		Parent[PY] = PX;
		Cnt[PX] += Cnt[PY];
		Cnt[PY] = 0;
	}
	else {
		Parent[PX] = PY;
		Cnt[PY] += Cnt[PX];
		Cnt[PX] = 0;
	}
}

void Input() {
	cin >> N >> M >> Q;
	Init();
	for (int i = 0; i < M; i++) {
		int X, Y;
		cin >> X >> Y;
		Line.push_back(make_pair(X, Y));
	}
	for (int i = 0; i < Q; i++) {
		int A;
		cin >> A;
		visited[A - 1] = true;
		S.push(A - 1);
	}
}

void Settings() {
	for (int i = 0; i < Line.size(); i++) {
		if (!visited[i]) {
			int X = Line[i].first;
			int Y = Line[i].second;
			if (Find(X) != Find(Y)) {
				Union(X, Y);
			}
		}
	}
	while (!S.empty()) {
		int A = S.top();
		S.pop();
		int X = Line[A].first;
		int Y = Line[A].second;
		int PX = Find(X);
		int PY = Find(Y);
		if (PX != PY) {
			answer += (Cnt[PX] * Cnt[PY]);
			Union(X, Y);
		}
	};
}

void Find_Answer() {
	cout << answer << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}