[알고리즘] Algospot_PICNIC

출처 : https://www.algospot.com/judge/problem/read/PICNIC

문제

안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다.

각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 봅니다. 예를 들어 다음 두 가지 방법은 서로 다른 방법입니다.

(태연,제시카) (써니,티파니) (효연,유리)
(태연,제시카) (써니,유리) (효연,티파니)

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 학생의 수 n (2 <= n <= 10) 과 친구 쌍의 수 m (0 <= m <= n*(n-1)/2) 이 주어집니다. 그 다음 줄에 m 개의 정수 쌍으로 서로 친구인 두 학생의 번호가 주어집니다. 번호는 모두 0 부터 n-1 사이의 정수이고, 같은 쌍은 입력에 두 번 주어지지 않습니다. 학생들의 수는 짝수입니다.

출력

각 테스트 케이스마다 한 줄에 모든 학생을 친구끼리만 짝지어줄 수 있는 방법의 수를 출력합니다.

정답코드

#include <bits/stdc++.h>

using namespace std;

int total(vector<vector<bool>>& v, vector<bool>& c, int n)
{
    int stand = -1;
    for(int i=0; i<n; i++)
    {
        if(!c[i])
        {
            stand = i;
            break;
        }
    }
    if(stand == -1)  return 1;

    int ret = 0;

    for(int start = stand + 1; start<n; start++)
    {
        if(!c[start] && v[stand][start])
        {
            c[start]=true;
            c[stand]=true;
            ret+=total(v,c,n);
            c[start]=false;
            c[stand]=false;
        }
    }
    return ret;
}

int main()
{
    int c,n,m;

    cin >> c;
    
    while(c--)
    {
        cin >> n >> m;

        vector<vector<bool>>v(n,vector<bool> (n,false));
        vector<bool> check(n,false);

        for(int i=0; i<m; i++)
        {
            int a,b;
            cin >> a >> b;
            v[a][b]=true;
            v[b][a]=true;
        }

        cout << total(v,check,n) << '\n';
    }

    return 0;
}

풀이 및 사고과정

책은 난이도 하라고 하는데 전혀 아니었다...
내 수준에서는 상당히 어려워 3시간 고민 끝에 책을 참고했다.
일단 아이디어는 비슷했으나 구현하지 못했고 구현했더라도 짝을 찾아서 세는 과정에서 중복이 발생했을 것이다. 아이디어를 코드로 구체화하는 연습이 많이 필요할 거 같다.