[완전 탐색] PICNIC

[1. 문제 재정의 및 추상화]

1. 학생들을 두명 씩 짝을 짓는다.
2. 단, 항상 서로 친구인 학생들 끼리만 짝을 지어야 한다.
3. 각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어진다.
4. 학생들을 짝 짓는 경우의 수를 계산해야 한다.
5. 학생 수는 최소 2명에서 최대 10명이고, 친구 쌍에 대해서 같은 쌍은 입력에 두번 주어지지 않는다.
6. 64MB 이하의 메모리를 사용해야하고, 1초 내 실행되어야 한다.

 

[2. 해결 계획]

1. 가능한 경우의 수를 계산해야 하므로, 완전 탐색 방식을 사용해 본다.
2. 재귀 호출을 이용해 완전 탐색을 해야하므로, 각 답을 만드는 과정을 여러개의 조각으로 나눈다.
   Base Case => 모든 학생이 짝을 지은 경우
3. 같은 학생을 두번 짝지어주는 것은 중복 되므로, 중복되지 않게 각 단계에서 남아있는 학생들 중 가장 번호가 빠른 학생의 짝을 먼저 찾아 주도록 한다.

 

[3. 계획 검증]

1. 답의 상한은 최대 10명의 학생이 모두 서로 친구인 경우로 이때 경우의 수는 9*7*5*3*1=945 이므로, 완전 탐색으로 충분히 해결 가능함.

 

[4. 구현]

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

bool table[10][10];

int countParings(std::vector<bool> &taken)
{
    // 아직 짝을 짓지 못한 학생을 찾는다.
    const auto itr = std::find(taken.begin(), taken.end(), false);
    // 모두 짝을 지었으므로, 한가지 경우를 완성했다.
    // base case
    if (itr == std::end(taken))
        return 1;

    // 짝을 지을 수 없는 경우, 0 이 반환된다.
    int ret = 0;
    const int start = std::distance(taken.begin(), itr);
    // 해당 학생 다음부터,  마지막 학생까지
    for (int next = start + 1; next < taken.size(); next++)
    {
        taken[start] = true; 
        // 현재 학생이 아직 짝을 짓지 않았고,
        // 타겟 학생과 짝이 가능한 경우
        if (!taken[next] && table[start][next])
        {
            // 짝을 짓고,
            taken[next] = true;
            // 다음 학생에 대해서 짝을 지어보도록 한다.
            ret += countParings(taken);
            // 이 학생과 짝을 그만두고, 다른 짝을 지어보도록 한다.
            taken[next] = false;
        }
        taken[start] = false;
    }

    return ret;
}

int main()
{
    int TC;
    int nm[2];

    scanf("%d", &TC);
    for (int N = 0; N < TC; N++)
    {
        scanf("%d %d", &nm[0], &nm[1]);
        memset(table, 0, sizeof(table));
        
        int y, x;
        for (int C = 0; C < nm[1]; C++)
        {
            scanf("%d %d", &y, &x);
            table[y][x] = true;
            table[x][y] = true;
        }
        std::vector<bool> taken(nm[0], false);
        printf("%d\n", countParings(taken));
    }  

    return 0;
}