백준 - 1765 닭싸움 팀 정하기

문제

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

1765번: 닭싸움 팀 정하기

내 친구의 친구는 내 친구이다.
내 원수의 원수도 내 친구이다.

해당 조건에 맞게 짠 가장 많은 팀 수를 구하는 문제였다.

 

문제 풀이

Union-Find 알고리즘을 이용해 풀었다. 친구와 원소 그래프 벡터를 따로 만들었고 조건에 맞게 makeUnion 해주는 과정을 반복했다. 

 

친구끼리는 makeUnion을 해줬으며 원수일 경우에는 해당 원수의 원수 리스트 모두에 대해 makeUnion을 해줬다. team 개수를 찾을 때에는 set을 이용해서 다른 parent를 가진, 즉 서로 다른 팀 개수를 쉽게 구할 수 있었다.

int N, M;

vector<vector<int>> friendG;
vector<vector<int>> enemyG;
vector<int> parent;
set<int> team;

int findParent(int a) {
	if (parent[a] == a) return a;

	return parent[a] = findParent(parent[a]);
}

void makeUnion(int a, int b) {
	int pa = findParent(a);
	int pb = findParent(b);

	parent[pb] = pa;
}

int main() {

	scanf("%d", &N);
	scanf("%d", &M);

	friendG = vector<vector<int>>(N+1, vector<int>());
	enemyG = vector<vector<int>>(N+1, vector<int>());
	parent = vector<int>(N + 1);

	for (int i = 0; i < N; i++) {
		parent[i] = i;
	}

	for (int i = 0; i < M; i++) {
		char r;
		int a, b;
		getchar();
		scanf("%c", &r);
		scanf("%d %d", &a, &b);

		if (r == 'E') {
			enemyG[a].push_back(b);
			enemyG[b].push_back(a);
		}
		else {
			friendG[a].push_back(b);
			friendG[b].push_back(a);
		}
	}

	for (int i = 1; i <= N; i++) {

		for (int j = 0; j < friendG[i].size(); j++) { //친구 -> 한 팀
			makeUnion(i, friendG[i][j]);
		}
		for (int j = 0; j < enemyG[i].size(); j++) { //원수 -> 원수의 원수와 한 팀
			int e = enemyG[i][j];
			for (int k = 0; k < enemyG[e].size(); k++) {
				makeUnion(i, enemyG[e][k]);
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		team.insert(findParent(i));
	}

	printf("%d", team.size());
	
	return 0;
}