[알고스팟 - PICNIC] 소풍

||문제 이해

총 학생수에서 친구관계인 학생들끼리 두명씩 묶어 나오는 경우의 수 구하기

단 순서 변경이나 중복은 허용되지 않는다.

---

||구현

set<int> friends[11];
bool check[11];

/* maxi - 총 학생 수
 * cnt - 짝을 지어야 하는 수, 짝을 지을때마다 감소하여 최종 0이 된다.
 * result - 문제의 결과 값
 */
void Counting(const int & maxi, int cnt, int & result)
{
	//모든 학생을 다 짝지었는지 확인
	if (cnt == 0)
	{
		++result;
		return;
	}

	//시작 할 학생 찾기
	int start;
	for (int i = 0; i < maxi; ++i)
	{
		if (check[i] == false)
		{
			start = i;
			break;
		}
	}

	//짝을 짓기
	for (int i = start + 1; i < maxi; ++i)
	{
		//start학생이 아니고 아직 짝이 지어지지 않았다면
		if (check[i] == false)
		{
			//서로 친구라면
			if (friends[start].find(i) != friends[start].end())
			{
				//짝을 지었다는 체크를 해주고
				check[start] = true;
				check[i] = true;

				//다음 학생을 찾는다.
				Counting(maxi, cnt - 1, result);
				
                //찾고나면 다시 체크를 풀어준다.
				check[start] = false;
				check[i] = false;
			}
		}
	}
}

---

||되돌아보기

이번 문제와 같이 항상 완전탐색을 너무 어렵게 생각하는 경향이 있다.

침착하게 차근차근 생각해보자

 

이런 같은 답을 중복으로 세는 상황에서 중복이 나오지 않게 세는 방법을 집중적으로 생각해보는것도 좋을 것 같다.

예로 묶음 0,1과 1,0이 같은 경우지만 다르게 인식하여 세고 있다면

미리 사전순으로만 묶음이 생기게 한다면 1,0 같은 경우는 나오지 않을거다.

 

즉, 특정 형태를 갖는 데이터들을 만드는것!

---

||개선 코드

종만북의 코드다

int n;
bool areFriends[10][10];

int Counting(bool taken[10])
{
	//가장 빠른 번호를 찾는다.
	bool first = -1;
	for (int i = 0; i < n; ++i)
	{
		if (taken[i] == false)
		{
			first = i;
			break;
		}
	}

	//기저 사례 : 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료한다.
	if (first == -1) return 1;

	int ret = 0;
	//짝지을 학생을 결정하기
	for (int second = first + 1; second < n; ++second)
	{
		if (taken[second] == false && areFriends[first][second])
		{
			taken[first] = taken[second] = true;
			ret += Counting(taken);
			taken[first] = taken[second] = false;
		}
	}
	return ret;
}