PICNIC (C언어)

PICNIC 문제를 C언어로 풀어보았다.

예전에 PS 처음할때는 정말 어려웠던 문제였다.

C 연습하려고 포인터를 이용해서 문제를 풀었다.

완전탐색을 이용해서 문제해결, 단 중복되는 경우를 없애야한다.

자기보다 번호가 큰 사람만을 보는 방법으로, 한 방향을 정해서 중복을 없앨 수 있었다.

<정답코드 C>

#include<stdio.h>
 
void init(int(*isfriend)[11], int* havefriend);
void matching(int k, int n, int(*isfriend)[11], int* havefriend,int* sum);
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc, sum;
    int t, i, n, m, f1, f2;
    int isfriend[11][11];
    int havefriend[11];
    scanf("%d", &tc);
    for (t = 1; t <= tc; t++)
    {
        sum = 0;
        init(isfriend, havefriend);
        scanf(" %d %d", &n, &m);
        for (i = 0; i < m; i++)
        {
            scanf(" %d %d", &f1, &f2);
            isfriend[f1][f2] = 1;
            isfriend[f2][f1] = 1;
        }
 
        matching(0, n, isfriend, havefriend, &sum);
 
        printf("%d\n", sum);
 
    }
 
 
 
    return 0;
}
void init(int(*isfriend)[11], int* havefriend)
{
    int i, j;
    for (i = 0; i < 11; i++)
        for (j = 0; j < 11; j++) {
            isfriend[i][j] = 0;
            havefriend[i] = 0;
        }
}
void matching(int k, int n, int(*isfriend)[11], int* havefriend, int* sum)
{
    int i, j;
 
    if (k == n)
    {
        for (j = 0; j < n; j++)
        {
            if (!havefriend[j])
                return;
        }
 
        (*sum)++;
        return;
    }
 
 
        for (i = k + 1; i < n; i++)
        {
            if (isfriend[k][i] && !havefriend[i] && !havefriend[k]) {
                havefriend[i] = havefriend[k] = 1;
                matching(k + 1, n, isfriend, havefriend, sum);
                havefriend[i] = havefriend[k] = 0;
            }
        }
    
    matching(k + 1, n, isfriend, havefriend, sum);
}