[BOJ/Gold 4] 백준 15809 전국시대(C++)

문제 링크

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

15809번: 전국시대

 

문제

전국시대엔 N개의 국가가 존재한다. 각 국가는 1부터 N까지의 번호를 가지고 있다.

또한, 모든 국가는 각자 자신의 국가의 힘을 상징하는 병력을 가지고 있다. 이때 M개의 기록이 주어진다. 각각의 기록은 다음과 같다.

1. 동맹 - 두 나라가 서로 동맹을 맺는다. 두 나라의 병력이 하나로 합쳐진다.
2. 전쟁 - 두 나라가 서로 전쟁을 벌인다. 병력이 더 많은 나라가 승리하며 패배한 나라는 속국이 된다. 이때 남은 병력은 승리한 나라의 병력에서 패배한 나라의 병력을 뺀 수치가 된다. 두 나라의 병력이 같을 경우 두 나라 모두 멸망한다.

모든 나라는 정직하기 때문에 내 동맹의 동맹도 나의 동맹이고, 내 동맹이 적과 전쟁을 시작하면 같이 참전한다. 속국인 경우도 동맹의 경우와 마찬가지이다.

따라서, 전쟁에서 진 국가와 동맹인 다른 국가 또한 전쟁에서 이긴 국가의 속국이 된다.

모든 기록이 끝났을 때 남아있는 국가의 수를 출력하고, 그 국가들의 남은 병력의 수를 오름차순으로 출력하는 프로그램을 작성하시오.

단, 여러 국가가 서로 동맹이거나 속국 관계인 경우는 한 국가로 취급한다.

입력

첫 번째 줄에 국가의 수를 나타내는 N과 기록의 수 M이 주어진다. (1 ≤ N, M ≤ 100,000)

두 번째 줄 부터 N개의 줄에 걸쳐 i번째 국가의 병력 Ai (1 ≤ i ≤ N)가 자연수로 주어진다. (1 ≤ Ai ≤ 10,000)

다음 M개의 줄에는 기록이 3개의 정수 O, P, Q로 주어진다. O가 1인 경우 P, Q가 서로 동맹을 맺었음을 의미하고, O가 2인 경우 P, Q가 서로 전쟁을 벌였음을 의미한다.

동맹끼리 다시 동맹을 맺거나 전쟁하는 입력은 주어지지 않는다.

출력

첫째 줄에 남아있는 국가의 수를 출력한다.

다음 줄에 각 국가의 남은 병력의 수를 띄어쓰기를 간격으로 오름차순으로 출력한다.

예제 입력 1

5 3
10
20
30
40
50
1 1 2
1 3 4
2 1 3

예제 출력 1

2
40 50

알고리즘 분류

• 유니온 파인드

풀이

동맹을 맺었다면 병력이 더 큰 나라에게 병력을 몰아주고, 전쟁을 했다면 병력이 더 큰 나라의 병력을 병력이 더 작은 나라의 병력만큼 빼고, 병력이 더 작은 나라의 병력을 0으로 만들었다. 만약 병력이 같다면 둘 다 Parent를 -1로 만들고 병력을 0으로 만들어주었다.

마지막으로 Parent가 자기 자신인 나라들의 수를 구하고, 병력을 오름차순해서 출력하였다.

코드

#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;
int A[MAX];
int Parent[MAX];
bool visited[MAX];
vector<int> Vec;
int answer = 0;

void Init() {
	for (int i = 0; i < MAX; i++) {
		Parent[i] = i;
	}
}

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

void Union_Country(int X, int Y) {
	int P_X = Find(X);
	int P_Y = Find(Y);
	if (A[P_X] >= A[P_Y]) {
		Parent[P_Y] = P_X;
		A[P_X] += A[P_Y];
		A[P_Y] = 0;
	}
	else {
		Parent[P_X] = P_Y;
		A[P_Y] += A[P_X];
		A[P_X] = 0;
	}
}

void Battle_Country(int X, int Y) {
	int P_X = Find(X);
	int P_Y = Find(Y);
	if (A[P_X] > A[P_Y]) {
		Parent[P_Y] = P_X;
		A[P_X] -= A[P_Y];
		A[P_Y] = 0;
	}
	else if (A[P_X] < A[P_Y]) {
		Parent[P_X] = P_Y;
		A[P_Y] -= A[P_X];
		A[P_X] = 0;
	}
	else {
		Parent[P_X] = -1;
		Parent[P_Y] = -1;
		A[P_X] = 0;
		A[P_Y] = 0;
	}
}

bool Comp(int A, int B) {
	return (A > B);
}

void Input() {
	Init();
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < M; i++) {
		int O, P, Q;
		cin >> O >> P >> Q;
		if (O == 1) { // O가 1이라면 P, Q 두 나라는 서로 동맹을 맺는다.
			if (Find(P) != Find(Q)) {
				Union_Country(P, Q);
			}
		}
		else if (O == 2) { // O가 2라면 P, Q 두 나라는 서로 전쟁을 한다.
			if (Find(P) != Find(Q)) {
				Battle_Country(P, Q);
			}
		}
	}
}

void Find_Answer() {
	for (int i = 1; i <= N; i++) {
		int Cur = Find(i);
		if (i == Cur) {
			answer++;
			Vec.push_back(A[Cur]);
		}
	}
	sort(Vec.begin(), Vec.end());
	cout << answer << "\n";
	for (int i = 0; i < Vec.size(); i++) {
		if (Vec[i] != 0) {
			cout << Vec[i] << " ";
		}
	}
	cout << "\n";
}

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

	return 0;
}