[Algospot] PICNIC

9093 단어 algospotalgospot

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

#include <iostream>
#include <cstring>
using namespace std;

int cnt=0;
int isFriend[11][11];
bool isPair[11];

void findPair(int num){
  int sum=0;
  for(int k=0; k<num; k++){
    sum += isPair[k];
  }
  if (sum == num){
    cnt++;
    return;
  }
  for(int i=0; i<num; i++){
    for(int j=0; j<num; j++){
      if(!isPair[i] && !isPair[j] && isFriend[i][j]){
        isPair[i] = isPair[j] = true;
        findPair(num);
        isPair[i] = isPair[j] = false;
      }   
    }
  }
}

int main(){
  int test, num, pair;
  
  cin >> test;

  while (test--){
    cnt = 0;
    cin >> num >> pair;

    memset(isFriend, 0, sizeof(isFriend));
    memset(isPair, 0, sizeof(isPair));

    while(pair--){
      int x,y;
      cin >> x >> y;
      isFriend[x][y] = 1;
    } 

    findPair(num);
    int i = num / 2;
    while (i){
      cnt /= i;
      i--;
    }
    
    cout << cnt << endl;
  }
}

처음에 중복을 해결해주지 않아 무시무시한 수가 나왔다.

책에서는

isFriend[x][y] = 1;
isFriend[y][x] = 1;

다음과 같이 했지만 이럴 경우 짝(1,2)와 짝(2,1) 을 다른 경우로 취급하기에 한번만 값을 넣었다.

또한 [(1,2), (3,4)], [(3,4), (1,2)] 처럼 중복이 되므로
결과를 (전체학생수/2)!로 나누어 주어야한다

좋은 웹페이지 즐겨찾기