백준 4195번: 친구 네트워크 (C++)

 

 

 

{"mean":["develop\n \t\t\t\n\t \t(←development)<br/><br/>[동사]\n\t\t ~ (sth) (from sth) (into sth)\n\t\t \t\t성장[발달]하다[시키다]","development\n \t\t\t\n\t \t(←develop)<br/><br/>[명사]\n\t\t \t\t발달, 성장","step<br/><br/>[명사]\n\t\t \t\t(발)걸음\n\n\t\t 참조 footstep, goose-step","by<br/><br/>[전치사]\n\t\t \t\t… 옆[가]에","go\n \t\t\t\n\t \t(←goes)<br/><br/>[동사]\n\t\t \t\t(한 장소에서 다른 장소로) 가다"],"word":"\n\t\t\t\t\t\tdevelop\n \t\t\t\n\t \t(←development)\n\t ","soundUrl":"https://dict-dn.pstatic.net/v?_lsu_sa_=350823562d933a56e49151a5328451fbcd696f25a3026f686a32f271fbcc6da1cf5227ac6ca5da71e9076c25552d10691293271f38cb5d0bfc8e87758f046258e99e00b604d2d4302eb7ee1098d20b26c055a2c3ae5c7edcaa16937e6186b0f53b111395a53b44d182fe9b16c3a8c94b419f282b738072b275a445b877a3e8bb","phoneticSymbol":"[dɪˈveləp]"}

 

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

4195번: 친구 네트워크

 

 

각 친구의 이름은 그래프의 노드라 생각하면, 각 입력은 그래프의 edge가 된다. 출력은 해당 그래프에 속하는 노드 갯수가 된다.

그래프 문제라고 생각하는것보다 집합문제로 생각하면 훨씬 쉽다. 각 원소의 집합의 포함관계를 알 수 있는 union-find 알고리즘을 사용하기로 하였다.

 

union-find 알고리즘에 대해서는 아래 링크를 참고하자. 다른분의 블로그인데 잘 정리 해놓으셨다.

https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

[알고리즘] Union-Find 알고리즘 - Heee's Development Blog

 

 

보통 union-find 알고리즘은 숫자로 노드와 root를 표기하는데 이름이 string 타입이다 보니 그러기 쉽지않다. 그래서 array 타입 대신 map 타입을 이용을 하기로 마음먹었고 보다 속도를 높이기 위해 c++ stl의 map 대신에 unordered_map을 사용하기로 마음먹었다. 둘의 차이는 map 자료구조는 key값에 따라 항상 데이터가 정렬된 상태로 저장되지만 unordered_map은 그렇지 않다. 굳이 정렬된 상태로 저장할 필요가 없으니 후자를 쓴다.

 

string find(string a){
	if(um[a] == a){
		return a;
	}
	else{
		return um[a] = find(um[a]);
	}
}

void uni(string a, string b){
	string A = find(a);
	string B = find(b);

	if(A==B) return;

	um[B] = A;
	nums[A] += nums[B];
}

union-find 함수의 핵심은 find 함수와 union 함수인데 위와 같이 구현하였다. 예리하신분은 알겠지만 find함수같은 경우 최악의 경우를 방지하기 위해 최적화된 find지만 union 함수같은 경우 그렇지 않다. find 최적화 만으로 충분히 시간내에 풀릴것 같아서 union은 최적화 하지 않았다.

 

전체 코드는 아래와 같다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <unordered_map>

typedef long long ll;

using namespace std;
unordered_map<string, string> um;
unordered_map<string, int> nums;


string find(string a){
	if(um[a] == a){
		return a;
	}
	else{
		return um[a] = find(um[a]);
	}
}

void uni(string a, string b){
	string A = find(a);
	string B = find(b);

	if(A==B) return;

	um[B] = A;
	nums[A] += nums[B];
}

int main(int argc, char** argv)
{	

	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int tn;
	cin >> tn;

	while(tn--){
		int n;
		cin >> n;

		um.clear();
		nums.clear();
		
		for(int i=0; i<n; i++){
			string a, b;
			cin >> a >> b;
			if(um.count(a) == 0){
				um.insert(make_pair(a, a));
				nums.insert(make_pair(a,1));
			}
			if(um.count(b) == 0){
				um.insert(make_pair(b, b));
				nums.insert(make_pair(b,1));
			}
			uni(a,b);
			cout << nums[find(a)] << '\n';

		}
	}
	
	
	
}