[PICNIC] 소풍

[PICNIC] 소풍 : https://algospot.com/judge/problem/read/PICNIC

### 완전탐색 ###

<소스코드>

picnic(k) : k 명의 짝이 정해졌을 때, n-k 명으로 짝을 지을 수 있는 경우의 수..

#include <stdio.h>
#include <string.h>
 
int isFriend[11][11];
int n, hasPair[11];
 
int findA()
{
    for(int i=0; i<n; i++)
        if(!hasPair[i])
            return i;
    return n;
}
 
int picnic(int k)
{
    int a, ret = 0;
    if(k == n) return 1;
    
    a = findA();
    hasPair[a] = 1;
 
    for(int i=0; i<n; i++) {
        if(isFriend[a][i] && !hasPair[i]) {
            hasPair[i] = 1;
            ret += picnic(k+2);
            hasPair[i] = 0;
        }
    }
    hasPair[a] = 0;
    return ret;
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int m, ans=0;
        scanf("%d%d", &n, &m);
        
        memset(isFriend, 0, sizeof(isFriend));
        while(m--) {
           int a, b;
           scanf("%d%d", &a, &b);
           isFriend[a][b] = isFriend[b][a] = 1;
        }
        printf("%d\n", picnic(0));
    }
    return 0;
}

>> 쉬운듯 쉽지 않은 듯..

>> 이런 문제를 풀 때는 (0, 1) 과 (1, 0)을 따로 세면 안된다고 한다.

>> 또한 (0, 1)을 세고, (2, 3)을 센 것과 (2, 3)을 먼저 세고 (0, 1)을 센 것고 같은 방법임에 유의해야 한다고 한다.

>> 항상 특정 형태를 갖는 답만 세는 것이 중요..!!

>> 같은 답 중에서 사전순으로 가장 먼저 오는 답 하나만을 세기.

>> 각 단꼐에서 남아있는 학생들 줄 가장 번호가 빠른 학생의 짝을 찾아주면 된다고 한다.

>> 이렇게 하면 위 두가지 경우의 문제점을 모두 해결할 수 있다고 한다.

>> 별 차이는 없지만, 이런식으로 작성해도 된다.

#include <stdio.h>
#include <string.h>
 
int isFriend[11][11];
int n, hasPair[11];
 
int findA()
{
    for(int i=0; i<n; i++)
        if(!hasPair[i])
            return i;
    return n;
}
 
int picnic()
{
    int a, ret = 0;
    
    a = findA();
    if(a == n) return 1;
 
    hasPair[a] = 1;
 
    for(int i=0; i<n; i++) {
        if(isFriend[a][i] && !hasPair[i]) {
            hasPair[i] = 1;
            ret += picnic();
            hasPair[i] = 0;
        }
    }
    hasPair[a] = 0;
    return ret;
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int m, ans=0;
        scanf("%d%d", &n, &m);
        
        memset(isFriend, 0, sizeof(isFriend));
        while(m--) {
           int a, b;
           scanf("%d%d", &a, &b);
           isFriend[a][b] = isFriend[b][a] = 1;
        }
        printf("%d\n", picnic());
    }
    return 0;
}

>> 매개변수를 없애고, 탈출조건이 조금 변경되었다.

>> 모두 짝이 있다면 하나의 경우의 수가 완성된 셈이다.