종만북 P.155 소풍(brute force)

#include <iostream>
#include <cstring>
 
using namespace std;
 
int n;
bool areFriends[10][10];
 
int countPairings(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 += countPairings(taken);
            taken[firstFree] = taken[pairWith] = false;
        }
    }
    return ret;
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int count;
    cin >> count;
    while (count--)
    {
        int pairofStudents;
        cin >> n >> pairofStudents;
        while (pairofStudents--)
        {
            int tmp1, tmp2;
            cin >> tmp1 >> tmp2;
            areFriends[tmp1][tmp2] = true;
            areFriends[tmp2][tmp1] = true;
        }
        bool freinds[10] = {
            0,
        };
        int answer = countPairings(freinds);
        cout << answer << "\n";
        memset(areFriends, 0, sizeof(areFriends));
    }
}

 

너무 어렵다... 함수 내부의 코드를 이해하고 문제를 풀긴 했지만 만약 혼자 이런 문제를 만났을 때 풀 수 있을지 잘 모르겠다. 

이 문제에서 가장 재밌었던 부분은 int firstFree=-1; 을 통해 강제로 번호가 가장 빠른 학생을 찾아서 중복을 제거하는 부분이다.  이 선언을 통해 첫번째 for loop를 돌았을 때 firstFree가 아직 -1이라면 기저 사례에 해당하게 되면서 프로그램이 종료된다. 

백준 문제를 풀면서는 한번에 테스트 케이스가 여러개 들어오는 경우가 별로 없었어서 초기화 부분은 잘 신경쓰지 않았었는데 이 문제에서는 여러개의 테스트 케이스가 들어올 수 있음으로 초기화 하는 부분이 필요했다. 29, 57이 그런 일을 해주는 부분이다.

시간 제한은 1초이고 테스트 케이스의 개수는 50개 이하, n은 최대 10이므로 어떤 시간복잡도가 나와도 1초는 절대 넘지 않을 것 같다.