ID : PICNIC 난이도 : 하 (재귀 완전탐색) (느림)

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

#include <iostream>
#include <vector>
 
 
class Friends
{
public:
    int cFriendNum;
    int cPairNum;
    int cNumOfOrder;
    bool cFirendly[10][10] = { { false } };
 
    int CountPairings(bool* , Friends& );
 
};
 
int main()
{
    int nTestCase;
    int nFriendNum;
    int nPairNum;
 
    std::vector<Friends> nFriendList;
    nFriendList.clear();
 
    std::cin >> nTestCase;
    getchar();
 
    for (int i = 0; i < nTestCase; ++i)
    {
        Friends nTmpFriends;
        std::cin >> nFriendNum >> nPairNum;
        getchar();
 
        nTmpFriends.cFriendNum = nFriendNum;
        nTmpFriends.cPairNum = nPairNum;
 
        for (int j = 0; j < nPairNum; ++j)
        {
            int nTmp1, nTmp2;
            std::cin >> nTmp1 >> nTmp2;
            nTmpFriends.cFirendly[nTmp1][nTmp2] = true;
        }
        
        nFriendList.push_back(nTmpFriends);
 
 
    }
    
 
    for (auto& nFriendCase : nFriendList)
    {
        bool nTaken[10] = { false };
        
        nFriendCase.cNumOfOrder = nFriendCase.CountPairings(nTaken,nFriendCase);
 
    }
 
    for (auto nFriendCase : nFriendList)
    {
        std::cout << nFriendCase.cNumOfOrder << std::endl;
    }
 
        
 
    return 0;
}
 
int Friends::CountPairings(bool* taken, Friends& nFriend)
{
    //남은 학생들 중 가장 번호가 빠른 학생을 찾는다.
    int firstFree = -1;
    for (int i = 0; i < nFriend.cFriendNum; ++i)
    {                
        if (!taken[i])
        {
            firstFree = i;
            break;
        }
    }
 
    //기저사례 : 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료한다.
    if (firstFree == -1) return 1;
 
    int ret = 0;
 
    //이 학생과 짝지을 학생을 결정한다.
    for (int pairWith = firstFree + 1; pairWith < nFriend.cFriendNum; ++pairWith)
    {
        if (!taken[pairWith] && nFriend.cFirendly[firstFree][pairWith])
        {
            taken[firstFree] = taken[pairWith] = true;    //firstFree 와 pairWith 번째 친구를 사용했다는 표시
            ret += CountPairings(taken, nFriend);
            taken[firstFree] = taken[pairWith] = false;  // 다음번 순서를 찾기위해 사용했다는 표시 제거
        }
    }
 
    return ret;
}