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

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

4195번: 친구 네트워크

---

 

---

접근 방법

각각의 문자가 들어올 때 map의 기능을 활용하여 , 이미 등록이 되어있는지 확인을 해준다.

이미 들어왔던 문자열이면 그 문자열의 value를 반환해주고, 새로 들어오는 문자열이면 새로운 value를 부여한 후 반환해준다.

이렇게 반환된 value들을 union find를 하여 연결을 시켜주면, 해결이 가능하다.

union find의 과정에서 각각의 자식들의 갯수도 합쳐주는 과정을 해야 한다.

---

코드

 

#include<iostream>
#include<string>
#include<vector>
#include<map>
using namespace std;
map<string,int> m;
map<string, int>::iterator it;
int n;
string s1,s2;
int counter;
int par[100000];
int chi[100000];
int find(int x) { //부모를 find하는 과정,
//이 과정에서 부모를 여러번 거쳐서 가야하면 바로바로 업데이트 해준다.
	if (par[x] == x) {
		return x;
	}
	else {
		return par[x] = find(par[x]); //바로바로 업데이트 하는 과정
	}
}
int unionFun(int x, int y) //유니온 파인드 해주는 함수
{
	x= find(x);
	y = find(y);
	if (x != y) {
		if (x< y) { //부모의 값이 더 작은쪽으로 부모를 맞춰준다.
			par[y] = x;
			chi[x] += chi[y];
			return chi[x];
		}
		else {
			par[x] = y;
			chi[y] += chi[x];
			return chi[y];
		}
	}
	else { //부모가 같다면 연결할 필요가 없이 바로 자식의 갯수를 반환해줌
		return chi[x];
	}	
}
int main() {	
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	cin >> t;
	for (int a = 0; a < t; a++) {
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> s1 >> s2;
			int k1, k2;
			it = m.find(s1); //s1이라는 문자열이 map에 있는지 확인
			if (it != m.end()) { //맵에 있다면
				k1 = it->second; //맵에 있는 value를 k1에 저장
			}
			else { //맵에 없다면
				k1 = counter; //새로운 value를 생성후 맵에 삽입해준다.
				m.insert({ s1, counter });
				par[counter] = counter; //새로 생성되는 노드의 부모는 자기자신을 가르킴
				chi[counter] = 1; //새로 생성되는 노드의 자식의 갯수(자신 포함)은 한개
				counter++;
			}
			it = m.find(s2); //s1과 같은 과정
			if (it != m.end()) {	
				k2 = it->second;
			}
			else {
				k2 = counter;
				m.insert({ s2, counter });
				par[counter] = counter;
				chi[counter] = 1;
				counter++;
			}
			cout<<unionFun(k1, k2)<<'\n'; //위의 과정에서 반환한 두개의 값을 대입
		}
		m.clear();//테스트 케이스가 바뀔 때 마다 맵을 초기화해줘야함
	}
}

---

분리집합과 map을 동시에 사용하게 되는, 아이디어는 금방 떠올렸지만 생각보다 구현이 꽤 걸린 문제였다.