[c언어/c++] 소풍 (PICNIC) - 완전 탐색 알고리즘 (경우의 수)

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

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

#include<stdio.h>
#include<memory.h>

int n,m;
bool areFriends[10][10];
int count(bool[]);
int main(){
 
 int a;
 int b;
 int loop;

 scanf(" %d",&loop);
 
 for(int i = 0 ; i < loop ; i++){

  memset(areFriends, 0, sizeof(areFriends));
  scanf(" %d %d",&n,&m);

  for(int i = 0 ; i < m ; i++){
   scanf(" %d %d",&a,&b);
   areFriends[a][b]=true;
   areFriends[b][a]=true;
  }

  bool taken[10];
  
  memset(taken, 0, sizeof(taken));
  printf("%d\n",count(taken));
 
 }
 
 return 0;
}

int count(bool taken[10]){
 int firstFree = -1;
 for(int i = 0 ; i < n ; i++){
  if(!taken[i]){
   firstFree = i;
   break;
  }
 }

 if(firstFree == -1) return 1;

 int ret = 0;

 for(int pairWith = firstFree+1 ; pairWith < n ; pairWith++){
  if(!taken[pairWith] && areFriends[firstFree][pairWith]){
   taken[firstFree] = taken[pairWith] = true;
   ret = ret + count(taken);
   taken[firstFree] = taken[pairWith] = false;
  }
 }
 return ret;

}