[백준 4195번 C++풀이] - 친구 네트워크

걸린 시간 : 3시간 16분

한마디로 진짜 어려웠다.

일단 답을 찾아봤는데 답자체를 이해하질 못해서 그냥 내 방식대로 차근차근 진행하며 풀었다.

일단, 처음에는 map으로 처음 친구가 있을경우 둘다 2로, 아닐 경우, 가장 많은 친구에 1을 더한후 다른 친구도 그 값을 같게 하였으나, 틀리고 시간초과 나서 일단 a b, b c,c a,할경우 5가 나오는 문제부터 해결하기 위해, set을 만들어서 그곳에 같은 친구들끼리 뭉치게 넣고, 두 그룹이 만나면 한 그룹에 다른 그룹을 넣는 식으로 처리하고, 그 그룹의 친구수는 따로 map을 만들어서 했으나, 그 후에 시간복잡도가 너무 올라가 그냥 포인터처럼 배열 번호 저장해서 출력하는 식으로 처리했다.

이 문제를 3시간동안 잡고 푸니 짜증나긴 하지만, 굉장히 기분이 좋다 ㅎㅎ

 

#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;


int main()
{

	int a, b;
	char fr3[22], fr4[22];
	string fr1, fr2;
	scanf("%d", &a);
	for (int i = 0; i < a; i++)
	{
		map <string, int> s;
		map <string, int> tems;
		vector <int> fr(100001, -1);
		vector <set<string>> t;
		t.push_back({""});
		scanf("%d", &b);
		int check = 0;
		for (int j = 0; j < b; j++)
		{


			scanf("%s", fr3);
			scanf("%s", fr4);


			fr1 = fr3;
			fr2 = fr4;

			if (fr[tems[fr1]] != -1 && fr[tems[fr2]] != -1)
			{
				bool tr = 0;
				int wnth2 = tems[fr2];
				int wnth1 = tems[fr1];
				if (tems[fr1] != tems[fr2])
				{
					int f1 = s[fr1], f2 = s[fr2];

					if (t[wnth2].size() > t[wnth1].size())
					{
						fr[tems[fr2]]+= fr[tems[fr1]];
						for (auto k : t[wnth1])
						{
							tems[k] = tems[fr2];
							t[wnth2].insert(k);

						}
						t[wnth1] = {};
						fr[tems[fr1]] = fr[tems[fr2]];


					}
					else
					{
						fr[tems[fr1]] += fr[tems[fr2]];
						for (auto k : t[wnth2])
						{
							s[k] = f1 + f2;
							tems[k] = tems[fr1];
							t[wnth1].insert(k);

						}
						t[wnth2] = {};
						fr[tems[fr2]] = fr[tems[fr1]];

					}




				}
			}
			else if (fr[tems[fr1]] != -1 && fr[tems[fr2]] == -1)
			{
				t[tems[fr1]].insert(fr2);
				tems[fr2] = tems[fr1];
				fr[tems[fr1]]++;


			}
			else if (fr[tems[fr1]] == -1 && fr[tems[fr2]] != -1)
			{
				t[tems[fr2]].insert(fr1);
				tems[fr1] = tems[fr2];
				fr[tems[fr2]]++;
			}
			else if (fr[tems[fr1]] == -1 && fr[tems[fr2]] == -1)
			{
				set <string> tem;
				tem.insert(fr1);
				tem.insert(fr2);
				t.push_back(tem); //s[글자]는 원래는 친구 개수였으나, 친구개수는 friend 에 저장할 것 이므로 쓸모가 없어짐.
				tems[fr1] = check+1;//tems에 배열 위치가 저장 되고 있음. 이걸 활용해 값을 가르키는 주소를 만들자.
				tems[fr2] = check+1;
				fr[check+1] = 2;
				check++;
			}
			printf("%d\n", fr[tems[fr1]]);
		}

	}
}