[백준/BOJ] 백준 16402번 : 제국

www.acmicpc.net/problem/16402

16402번: 제국

map을 이용한 유니온 파인드를 통해 문제를 해결했다. cin은 '\n(엔터)'을 담지 않고, getline은'\n(엔터)'을 담아서 getline에'\n(엔터)'가 들어가게 되는 문제 해결을 위해 위해 cin.ignore()가 쓰였다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
using namespace std;

int n, m;
map<string, string> parent;
map<string, string>::iterator it;

string Find(string u)
{
	if (u == parent[u])
		return u;

	return parent[u] = Find(parent[u]);
}

void Merge(string u, string v) //u을 v에 합침
{
	u = Find(u);
	v = Find(v);

	parent[u] = v;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;
	cin.ignore(); //cin은 '\n(엔터)'을 담지 않고, getline은'\n(엔터)'을 담아서 getline에'\n(엔터)'가 들어가게 되는 문제해결을 위해 위해 cin.ignore()필요

	for (int i = 0; i < n; i++)
	{
		string input;
		getline(cin, input);

		parent.insert(make_pair(input, input));
	}

	for (int i = 0; i < m; i++)
	{
		string input;
		getline(cin, input);

		bool one_find = false;
		string one = "";
		string two = "";
		for (int j = 0; j < input.size() - 2; j++)
		{
			if (one_find == false)
			{
				if (input[j] == ',')
				{
					one_find = true;
					continue;
				}

				else
				{
					one += input[j];
					continue;
				}
			}

			else
			{
				two += input[j];
			}
		}

		if (input[input.size() - 1] == '1')
		{
			if (Find(one) != Find(two))
				Merge(two, one);

			else //속국이 자신의 종주국을 공격하는 경우
			{
				parent[two] = one;
				parent[one] = one;
			}
		}

		else
		{
			if (Find(one) != Find(two))
				Merge(one, two);

			else //속국이 자신의 종주국을 공격하는 경우
			{
				parent[one] = two;
				parent[two] = two;
			}
		}

		for (it = parent.begin(); it != parent.end(); it++)
		{
			Find((*it).first);//업데이트
		}
	}

	vector<string> result;
	for (it = parent.begin(); it != parent.end(); it++)
	{
		if ((*it).first == (*it).second)
			result.push_back((*it).first);
	}

	cout << result.size() << "\n";
	for (int i = 0; i < result.size(); i++)
	{
		cout << result[i] << "\n";
	}


	return 0;
}