BOJ - 16402번 제국(C++)

문제 출처: https://www.acmicpc.net/problem/16402

문제 난이도

Gold 1

문제 접근법

왕국끼리 싸워서 남은 종주국을 출력하는 문제이므로 저절로 트리, 즉 부모 노드가 떠올랐다.
그래서 집합의 한 종류이자 부모 노드를 알 수 있는 Union&Find 알고리즘을 사용했다.
이에 관한 개념만 알고 기본 문제를 풀어봤다면 충분히 풀 수 있는 문제.

통과 코드

#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_map>
#include <set>

using namespace std;

unordered_map<string, string> contry;

string Find(string v) {
	if (contry[v] == v) return v;
	return contry[v] = Find(contry[v]);
}

void Union(string c1, string c2) {
	string a = Find(c1);
	string b = Find(c2);
	if (a != b) {//다른 왕국끼리 싸웠을 때,
		contry[a] = b;
		for (auto x : contry) { //속국까지 자기 나라로 점령
			if (x.second == a) {
				contry[x.first] = b;
			}
		}
	}
	else {
		//내부 분열 일 때,
		for (auto x : contry) { //자기 나라로 점령
			if (x.second == a) {
				contry[x.first] = c2;
			}
		}
	}
}

int main() {
	int N, M;
	cin >> N >> M;
	getchar();
	for (int i = 0; i < N; i++) {
		string str;
		getline(cin, str);
		contry[str.substr(11)] = str.substr(11);
	}
	for (int i = 0; i < M; i++) {
		string res;
		getline(cin, res);
		string one = res.substr(11, res.find(',') - 11);
		res = res.substr(res.find(',')+1);
		string two = res.substr(11, res.find(',') - 11);
		res = res.substr(res.find(',') + 1);
		if (res == "1") {
			Union(two, one);
		}
		else if (res == "2") {
			Union(one, two);
		}
	}
	set<string> s;
	for (auto x : contry) {
		s.insert(x.second);
	}
	cout << s.size() << "\n";
	for (auto x : s) {
		cout <<"Kingdom of " << x << "\n";
	}
	return 0;
}

피드백

처음에 런타임에러가 났는데 혹시나하고

ios_base::sync_with_stdio(false);
cin.tie(NULL);

이 부분을 지웠더니 통과했다. 아무래도 위의 코드는 는 C와 C++ 버퍼의 동기화를 끊는 거기 때문에 getline(cin, str) 에서는 오류가 난다. 혹시 나와 같이 런타임에러가 난다면 이 코드 구문을 지워보자!