알고리즘
[Algospot] PICNIC
병인
2021. 1. 31. 14:00
algospot.com :: PICNIC
소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로
algospot.com
#include <iostream>
using namespace std;
bool isFriends[10][10] = {false};
int n,m;
int DFS(bool isCheck[10]) {
int cur = -1;
for(int i = 0;i<n;++i) {
if(!isCheck[i]){
cur = i;
break;
}
}
if(cur==-1) {
return 1;
}
int result = 0;
for(int i = cur+1;i<n;++i) {
if(!isCheck[i] && isFriends[cur][i]) {
isCheck[cur] = true;
isCheck[i] = true;
result += DFS(isCheck);
isCheck[cur] = false;
isCheck[i] = false;
}
}
return result;
}
int main(int argc, const char * argv[]) {
int C;
cin>>C;
for(int tc = 0;tc<C;++tc) {
for(int i = 0;i<10;++i){
for(int j = 0;j<10;++j) {
isFriends[i][j] = false;
}
}
cin>>n>>m;
for(int i = 0;i<m;++i){
int a,b;
cin>>a>>b;
if(a<b) {
isFriends[a][b] = true;
} else {
isFriends[b][a] = true;
}
}
bool isCheck[10] = {false};
cout<<DFS(isCheck)<<"\n";
}
return 0;
}