[알고스팟/C,C++] PICNIC: 소풍

www.algospot.com/judge/problem/read/PICNIC

algospot.com :: PICNIC

예제 입력인 n : 4, m : 6, 친구 쌍 : 0 1 1 2 2 3 3 0 0 2 1 3 으로 살펴보겠습니다. 해당 경우에 모든 친구가 서로 짝입니다. 나올 수 있는 쌍은 [0, 1], [2, 3]과 [0, 2], [1, 3] 그리고 [0, 3], [1, 2]가 있습니다. 주의해야 할 점은 [0, 1]과 [1, 0]은 서로 같은 친구끼리 짝이 지어진 것이고, [2, 3], [0, 1] 또한 [0, 1], [2, 3]과 같은 방법으로 짝을 지어준 것입니다. [1, 0]과 같은 짝이 나오지 않게 하기 위해선 짝을 뽑을 때 오름차순으로만 뽑으면 됩니다. 그리고 각각의 쌍에 앞번호가 대표 번호라고 가정했을 때 쌍의 대표 번호도 오름차순으로만 뽑으면 중복은 사라집니다. [2, 3], [0, 1]의 경우 각 대표번호가 2, 0인데 내림차순이므로 뽑지 않으면 됩니다.

void dfs(int cnt, int num)
{
    if (cnt == n / 2) {
        res++;
        return;
    }

    if (!DP[num]) {
        for (int i = num + 1; i < n; i++) {
            if (pairs[num][i] && !DP[i]) {
                DP[num] = true;
                DP[i] = true;
                dfs(cnt + 1, num + 1);
                DP[num] = false;
                DP[i] = false;
            }
        }
    }
    else dfs(cnt, num + 1);

    return;
}

0번부터 시작해 짝을 정한다고 봅시다. 0번은 자기보다 큰 번호부터 탐색하며 짝이 될만한지 검사합니다. 먼저 해당 번호와 친구 사이가 맞는지(pairs[num][i]), 해당 번호가 아직 짝지어지지 않았는지(!DP[i]) 검사하여 조건을 통과한다면 다음 번호를 파라미터로 넘겨주며 자기 자신을 재귀 호출합니다. dfs(1, 1)이 실행되죠. 하지만 1번은 이미 짝지어졌기 때문에 조건을 통과하지 못하고 dfs(1, 2)를 실행하게 됩니다.

#include<iostream>
#include<cstring>

using namespace std;

#define MAX 10

int pairs[MAX][MAX];
bool DP[MAX];
int res, n, m;

void dfs(int cnt, int num)
{
    if (cnt == n / 2) {
        res++;
        return;
    }

    if (!DP[num]) {
        for (int i = num + 1; i < n; i++) {
            if (pairs[num][i] && !DP[i]) {
                DP[num] = true;
                DP[i] = true;
                dfs(cnt + 1, num + 1);
                DP[num] = false;
                DP[i] = false;
            }
        }
    }
    else dfs(cnt, num + 1);

    return;
}

int main(void)
{
    int c; cin >> c;

    for (int i = 0; i < c; i++) {
        cin >> n >> m;
        memset(pairs, 0, sizeof(pairs));
        for (int j = 0; j < m; j++) {
            int a, b; cin >> a >> b;
            pairs[a][b] = 1;
            pairs[b][a] = 1;
        }
        res = 0;
        dfs(0, 0);
        cout << res << "\n";
    }

    return 0;
}