소풍

문제 : https://algospot.com/judge/problem/read/PICNIC

문제

안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다.

각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 봅니다. 예를 들어 다음 두 가지 방법은 서로 다른 방법입니다.

• (태연,제시카) (써니,티파니) (효연,유리)
• (태연,제시카) (써니,유리) (효연,티파니)

코드 ( C ++ ) 종만북 참조

#include <iostream>

#include <algorithm>

#include <vector>

#include <string>

using namespace std;

int n, m;

bool friends[10][10];

// check[i] = i번째 학생이 짝을 이미 찾았으면 true , 아니면 false

int areFriends(bool check[10])

{

// 남은 학생들 중 가장 번호가 빠른 학생을 찾는다.

int first = -1;

for (int i = 0; i < n; ++i)

{

if (check[i] == false)

{

first = i;

break;

}

}

// 기저 사례: 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료한다.

if (first == -1) return 1;

int ret = 0;

// 이 학생과 짝지을 학생을 결정한다.

for (int next = first + 1; next < n; ++next)

{

if (!check[next] && friends[first][next])

{

check[first] = check[next] = true;

ret += areFriends(check);

check[first] = check[next] = false;

}

}

return ret;

}

int main()

{

int C;

cin >> C;

while (C--)

{

memset(friends, 0, sizeof(friends));

cin >> n >> m;

for (int i = 0; i < m; ++i)

{

int n1, n2;

cin >> n1 >> n2;

friends[n1][n2] = true;

friends[n2][n1] = true;

}

bool check[10] = { 0, };

int ans = areFriends(check);

cout << ans << endl;

}

return 0;

}