[AOJ][C++] 소풍 - PICNIC

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

algospot.com :: PICNIC

종만북 대망의 첫번째 문제 소풍이다.

 

어느 유치원에서 소풍을 갈 때 두명씩 짝을 지어주는데 서로 친구가 아닌 학생들끼리 짝을 지어주면 서로 싸우기 때문에 무조건 친구들끼리만 짝을 지어줘야 하는 문제이다.

 

친하지 않은 학생들끼리 짝이되면 서로 알아가려고 하면 좋을텐데 안드로메다 유치원 익스프레스반은 상당히 보수적인 아이들이 모여있는 것 같아 보인다.

 

전체 테스트 케이스가 50번에 학생의 수가 10명이 최대기 때문에 완전탐색으로 풀 수 있다.

 

재귀를 이용해 완전탐색으로 구현했다.

 

종만북에서는 이 문제를 재귀의 각 깊이에서 그 다음 단계들의 재귀가 모두 종료되야지 원래의 단계에서 다음줄로 넘어가는 걸 이용해서 풀이했으므로 비슷한 방식으로 따라서 구현해보았다.

한 친구쌍을 선택하면 둘을 선택했다고 cheak배열에 표시하고 다음 깊이의 재귀에 넣은 뒤에 다음줄에서 바로 cheak배열에서 빼는 방식으로 모든 경우의 수를 탐색했다.

완전탐색을 구현할 때 유용한 방법인 것 같다.

 

#include <iostream>
#include <cstdio>
using namespace std;
int map[11][11], cheak[11];
int n, m, answer=0;

void solve(int now)
{
    if(now==n-1) // 기저상태 : 마지막 학생을 탐색할 때
    {
        for(int i=0;i<n;i++)
        {
            if(cheak[i]==0)
            {
                return;
            }
        }
        answer++;
        return;
    }
    else if(cheak[now]==1)
    {
        solve(now+1);
    }
    else
    {
        for(int i=now;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(map[i][j]==1 && cheak[i]==0 && cheak[j]==0)
                {
                    cheak[i]=1;
                    cheak[j]=1;
                    solve(i+1);
                    cheak[i]=0;
                    cheak[j]=0;
                }
            }
        }
    }
}

int main()
{
    int C;
    scanf("%d",&C);
    
    while(C--)
    {
        answer=0;
        for(int i=0;i<11;i++) // reset
        {
            cheak[i]=0;
            for(int j=0;j<11;j++)
                map[i][j]=0;
        }
        int a, b;
        scanf("%d %d",&n,&m);
        for(int i=0;i<m;i++)
        {
            scanf("%d %d",&a,&b);
            map[a][b]=1;
            map[b][a]=1;
        }
        solve(0);
        printf("%d\n",answer);
    }
    return 0;
}