[C++] 알고스팟 - PICNIC

문제 링크

algospot.com :: PICNIC

 

풀이 )

  짝이 되는 경우 사람이 2명씩 빠지게 되므로 남는 인원이 2명씩 줄게 되고 0명이 되는 경우 모두 짝을 이루기 때문에 답을 1 증가시킨다.

  친구 관계를 나타내는 2차원 배열과 이미 짝이 만들어졌는지 여부를 확인할 배열을 만들어서 아직 짝이 아니고 친구 관계인 2명의 친구를 짝으로 만들어주고 다른 모든 방법에 대해 확인해 보기 위해 재귀함수 호출 이후 반복문이 돌기 전에 짝으로 만들어진 부분을 지워준다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int c, n, m;
int rel[10][10];
int visited[10];
int ans;

void rec(int remain){
  if(remain == 0){
    ans++;
    return;
  }

  int first, second;
  for(int i = 0; i < n-1; ++i){
    for(int j = i+1; j < n; ++j){
      if(rel[i][j] && !visited[i] && !visited[j]){
        visited[i]++;
        visited[j]++;
        rec(remain-2);
        visited[i]--;
        visited[j]--;
      }
    }
  }
}

int fac(int num){
  if(num < 3)
    return num;
  return num * fac(num-1);
}

int main(void){

  cin >> c;
  while(c--){
    cin >> n >> m;
    ans = 0;
    fill(visited, visited+n, 0);
    for(int i = 0; i < n; ++i)
      fill(rel[i], rel[i]+n, 0);
    for(int i = 0; i < m; ++i){
      int first, second;
      cin >> first >> second;
      rel[first][second] = 1;
      rel[second][first] = 1;
    }

    rec(n);
    ans /= fac(n/2);
    cout << ans << endl;
  }
}

 

주의점 )

• 재귀함수 속에서의 i와 j의 대소관계를 항상 유지하여 중복 제거
• ans /= fac(n/2)을 통해 짝의 순서로 인해 생기는 중복 제거