[BOJ/Gold 1] 백준 16402 제국(C++)

문제 링크

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

16402번: 제국

 

문제

배성일력 73년, 대륙을 주름잡던 성일 제국은 무리한 정복 전쟁 끝에 멸망하게 되었다. 기회를 노리던 반란군들은 혼란을 틈타 제각각 왕국을 선포했고, 왕국들은 제국의 자리를 차지하기 위해 수많은 전쟁을 치르게 되었다.

전쟁은 다음과 같은 방식으로 진행된다.

다른 왕국의 속국이 아닌 왕국은 자신의 속국이 아닌 다른 왕국을 공격하여 전쟁을 벌일 수 있다. 만약 전쟁에서 승리한다면 그 왕국과 그 왕국의 속국들을 전부 자신의 속국으로 삼게 된다. 때로는 다른 왕국의 속국을 공격하는 경우도 있는데, 이 경우 그 왕국의 종주국(그 왕국을 거느린 왕국)은 그 왕국을 지키기 위해 지원을 아끼지 않는다. 따라서 여기서 승리한다면 빈털터리가 된 종주국과 그 속국들까지도 전부 자신의 속국으로 삼을 수 있다. 그러나 전쟁에서 패배한다면 자신과 자신의 속국들이 전부 상대 왕국(만약 다른 왕국의 속국이라면 그 종주국)의 속국으로 넘어가게 된다.

속국은 기본적으로 다른 왕국을 공격할 수 없지만, 한 가지 예외가 있다. 바로 자신의 종주국을 공격하는 것이다. 만약 이 전쟁에서 속국이 승리한다면 속국 신세에서 벗어나 종주국이었던 왕국과 그 속국들을 속국으로 삼게 된다. 그러나 종주국이 승리한다면 아쉽게도 아무 일도 일어나지 않는다.

왕국들의 이름과 두 왕국의 전쟁 결과들이 주어질 때, 모든 전쟁이 끝난 후 속국이 아닌 왕국들의 수와 속국이 아닌 각 왕국의 이름을 출력하라.

입력

첫째 줄에 왕국들의 수 N(2 ≤ N ≤ 500), 전쟁 결과의 수 M(1 ≤ M ≤ 2,000) 이 주어진다.

둘째 줄부터 N개의 줄에 걸쳐 각 왕국의 이름이 주어진다.

왕국의 이름은 항상 “Kingdom of ”로 시작하며, 그 뒤로 공백 없는 하나의 단어로 이루어진다. 왕국 이름은 알파벳 대소문자와 공백으로만 이루어지고, 이름의 총 길이는 공백을 포함해 20을 넘지 않는다. 또한 왕국의 이름은 중복되지 않는다.

그다음 줄부터 M개의 줄에 걸쳐 전쟁의 결과가 주어진다.

전쟁의 결과로 왕국1의 이름, 왕국2의 이름, w(w = 1 or 2)가 공백 없이 쉼표(,)를 사이에 둔 형식으로 주어지며, w가 1인 경우 왕국1이, 2인 경우 왕국2가 승리했다는 것을 뜻한다. 왕국 이름의 입력 순서는 어느 쪽이 먼저 공격했는지와는 관계가 없으며, 문제 조건에 따라 성립할 수 있는 전쟁만이 입력으로 주어진다.

출력

첫째 줄에 속국이 아닌 왕국의 수를 출력한다.

둘째 줄부터 속국이 아닌 왕국의 이름을 ASCII 사전 순으로 정렬하여 한 줄에 하나씩 출력한다.

예제 입력 1

5 2
Kingdom of A
Kingdom of B
Kingdom of C
Kingdom of D
Kingdom of E
Kingdom of A,Kingdom of B,1
Kingdom of C,Kingdom of D,2

예제 출력 1

3
Kingdom of A
Kingdom of D
Kingdom of E

예제 입력 2

5 5
Kingdom of A
Kingdom of B
Kingdom of C
Kingdom of D
Kingdom of E
Kingdom of A,Kingdom of B,2
Kingdom of C,Kingdom of D,1
Kingdom of E,Kingdom of C,2
Kingdom of C,Kingdom of D,2
Kingdom of D,Kingdom of E,2

예제 출력 2

2
Kingdom of B
Kingdom of E

예제 입력 3

5 4
Kingdom of A
Kingdom of B
Kingdom of C
Kingdom of D
Kingdom of E
Kingdom of A,Kingdom of B,2
Kingdom of C,Kingdom of D,1
Kingdom of E,Kingdom of C,2
Kingdom of A,Kingdom of C,1

예제 출력 3

1
Kingdom of B

알고리즘 분류

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

풀이

우선 공백을 포함한 문자열을 받기 때문에 std::cin이 아닌 getline을 사용해야 한다.

왕국의 정보를 받고, map에 pair<string, int> 순서쌍을 삽입한다. 이 때 string은 왕국의 이름(Kingdom of 는 빼고, substr를 사용했음), int는 입력받은 순서(첫 번째로 입력받았으면 1)이다.

이제 M번에 걸쳐 전투의 정보를 처리하는데, 우선 Split 함수를 하나 선언하여 쉼표(,) 단위로 문자열을 Tokenize하면 문자열이 3개가 나올 것이다. 첫 번째 문자열은 첫 번째 왕국, 두 번째 문자열은 두 번째 왕국, 마지막 문자열은 전투의 결과(1이면 첫 번째 왕국의 승리, 2면 두 번째 왕국의 승리)이다.

이제 각 왕국이 종주국인지 아닌지를 조사할 것이다. 왕국의 Parent가 다르다면 무조건 두 왕국 다 종주국일 것이다. 속국은 오직 종주국과만 전투할 수 있다고 하였고, 문제에서 주어진 조건에 어긋나는 입력은 주어지지 않는다고 하였기 때문이다. 이제 전투를 벌여 1이면 두 번째 왕국의 Parent를 첫 번째 왕국으로 하고, 2면 그 반대로 한다.

왕국의 Parent가 같다면 속국과 종주국의 전투라는 뜻이다. 첫 번째 왕국이 종주국일 때, 전투의 결과가 2이거나, 두 번째 왕국이 종주국일 때, 전투의 결과가 1이라면 속국의 Parent를 자기 자신으로 하고 종주국의 Parent를 속국으로 한다. 즉 종주국과 속국이 바뀌는 것이다. 그 외의 경우는 따지지 않는다. 종주국이 속국을 이기면 아무 일도 일어나지 않는다고 하였기 때문이다.

종주국과 속국으로 만드는 과정은 유니온 파인드를 이용하면 된다.

그리고 마지막으로 속국이 아닌 왕국의 개수를 셀 때에는 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 501
#define LL long long
#define INF 1e9

using namespace std;
int N, M;
map<string, int> KM;
map<int, string> KM2;
int Parent[MAX];
int answer = 0;
vector<string> answerK;

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

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

void Union(int X, int Y, int Which) {
	int PX = Find(X);
	int PY = Find(Y);
	if (Which == 1) {
		Parent[PY] = PX;
	}
	else if (Which == 2) {
		Parent[PX] = PY;
	}
}

void Union2(int X, int Y, int Which) {
	int PX = Find(X);
	int PY = Find(Y);
	if (Which == 1) {
		Parent[X] = X;
		Parent[PY] = X;
	}
	else if (Which == 2) {
		Parent[Y] = Y;
		Parent[PX] = Y;
	}
}

vector<string> Split(string S) {
	vector<string> res;
	string tmp = "";
	for (int i = 0; i < S.size(); i++) {
		if (S[i] == ',') {
			res.push_back(tmp);
			tmp = "";
		}
		else {
			tmp += S[i];
		}
	}
	res.push_back(tmp);
	return res;
}

void Input() {
	cin >> N >> M;
	Init();
	string S;
	cin.ignore();
	for (int i = 1; i <= N; i++) {
		getline(cin, S);
		string Kingdom_Name = S.substr(11);
		KM.insert(make_pair(Kingdom_Name, i));
		KM2.insert(make_pair(i, Kingdom_Name));
	}
	for (int i = 0; i < M; i++) {
		getline(cin, S);
		vector<string> Info = Split(S);
		string K1 = Info[0].substr(11);
		string K2 = Info[1].substr(11);
		if (Find(KM[K1]) != Find(KM[K2])) { // 둘이 속국과 종주국 관계가 아닌 경우
			// 다른 왕국의 속국이 아닌 왕국은 자신의 속국이 아닌 다른 왕국을 공격하여 전쟁을 벌일 수 있다.
			Union(KM[K1], KM[K2], stoi(Info[2]));
		}
		else { // 속국이 종주국과 싸우는 경우(속국은 오직 종주국과만 싸울 수 있음)
			if (KM[K1] == Find(KM[K1])) { // 두 번째 왕국이 첫 번째 왕국의 종주국인 경우
				if (Info[2] == "2") { // 속국이 종주국을 이김
					Union2(KM[K1], KM[K2], 2);
				}
			}
			else if (KM[K2] == Find(KM[K2])) { // 첫 번째 왕국이 두 번째 왕국의 종주국인 경우
				if (Info[2] == "1") { // 속국이 종주국을 이김
					Union2(KM[K1], KM[K2], 1);
				}
			}
		}
	}
}

void Find_Answer() {
	for (int i = 1; i <= N; i++) {
		int P = Find(i);
		if (P == i) {
			answerK.push_back(KM2[i]);
		}
	}
	sort(answerK.begin(), answerK.end());
	cout << (int)answerK.size() << "\n";
	for (int i = 0; i < answerK.size(); i++) {
		cout << "Kingdom of " << answerK[i] << "\n";
	}
}

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

	return 0;
}