[BOJ/백준 1765/C++] 닭싸움 팀 정하기

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

1765번: 닭싸움 팀 정하기

 

[문제 요약]

- 닭싸움의 팀을 정하는 원칙은, 평소 학생들의 인간관계에 따라 다음과 같이 정리할 수 있다.

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

- 이 때 두 학생이 친구이면 같은 팀에 속해있어야 하며, 같은 팀에 속해 있는 사람들끼리는 전부 친구여야 한다.

- 학생들의 인간관계가 주어지면, 닭싸움을 위한 팀 정하기를 할 때, 최대 얼마나 많은 팀이 만들어질 수 있는지 알아내는 프로그램을 작성하시오.

 

[문제 조건]

- 첫째 줄에 학생의 수 n이 주어진다. 각 학생들은 1부터 n까지 번호가 매겨져 있다. (2 ≤ n ≤ 1000)

- 둘째 줄에 학생 간의 인간관계 중 알려진 것의 개수 m이 주어진다. (1 ≤ m ≤ 5000)

- 다음 m개의 줄에는 한 줄에 한 개씩, 학생 간의 인간관계가 F p q 혹은 E p q의 형태로 공백으로 구분되어 주어진다. (1 ≤ p < q ≤ n)

- 첫 번째 글자가 F인 경우에는 p와 q가 친구인 것이고, E인 경우는 p와 q가 원수인 경우이다. 

- 입력은 모순이 없음이 보장된다. 즉, 두 학생이 동시에 친구이면서 원수인 경우는 없다.

- 시간 제한 : 2초

- 메모리 제한 : 256MB

 

[문제 풀이]

이번 문제는 얼핏 보면 쉬운 문제 같아 보이지만 살짝 함정이 숨어 있는 그런 문제였다.

 

필자는 처음에 모든 노드들을 순차적으로 확인하면서 i번 노드의 친구의 친구, 원수의 원수만을 찾아서 같은 그룹으로 묶었으나 실패했다.

 

이유는 다음 그림을 보면 쉽게 이해할 수 있다.

다음과 같은 경우 처음방법으로 팀을 짜게 되면 1번은 2번하고만 팀이 결성된다.

 

하지만 2번이 1번과 같은 팀이 된 경우 2번의 원수의 원수인 4번도 같은 친구가 되어야하기 때문에 1,2,4 이렇게 한팀이 되어야 한다. 따라서 새로 추가된 친구에 대해서도 문제에서 주어진 2개의 조건을 다시 확인해야 문제를 정확히 풀 수 있다.

 

[소스 코드]

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

#define INF 987654321
#define pii pair<int,int>

using namespace std;

int n, m;
vector<vector<int>> fri;
vector<vector<int>> enemy;
vector<bool> ck;

void find_fri(int cur)
{
	for (int i = 0; i < fri[cur].size(); i++)
	{
		if (ck[fri[cur][i]]) continue;
		ck[fri[cur][i]] = true;
		find_fri(fri[cur][i]);
	}

	for (int i = 0; i < enemy[cur].size(); i++)
	{
		int my_enemy = enemy[cur][i];
		for (int j = 0; j < enemy[my_enemy].size(); j++)
		{
			if (ck[enemy[my_enemy][j]]) continue;
			ck[enemy[my_enemy][j]] = true;
			find_fri(enemy[my_enemy][j]);
		}
	}
}

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

	cin >> n >> m;

	ck.resize(n + 1);
	fri.resize(n + 1); enemy.resize(n + 1);

	for (int i = 0; i < m; i++)
	{
		char op;
		int tmp1, tmp2;
		cin >> op >> tmp1 >> tmp2;

		if (op == 'F')
		{
			fri[tmp1].push_back(tmp2);
			fri[tmp2].push_back(tmp1);
		}
		else
		{
			enemy[tmp1].push_back(tmp2);
			enemy[tmp2].push_back(tmp1);
		}
	}

	int cnt = 0;
	for (int i = 1; i <= n; i++)
	{
		if (ck[i]) continue;
		find_fri(i);
		cnt++;
	}
	cout << cnt;
}

굳