[Algospot] 소풍(PICNIC)

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

algospot.com :: PICNIC

 

재귀 연습 문제이다.

#include <stdio.h>
 
const int maxN = 15;
 
int c, n, m;
int pair[maxN][maxN];
 
void initPair() {
    for(int i =0; i<maxN; i++) {
        for(int j=0; j <maxN; j++) 
            pair[i][j]=0;
    }
}
 
int nextChild(int child[], int point) {
    for(int i = point; i<n; i++) {
        if(child[i]==1)return i;
    }
    return -1;
}
 
void makePair(int child[], int leftChild, int* numPair) {
    int pointChild= nextChild(child, 0); //standard point
    //printf("%d pc \n", pointChild);
    if(leftChild==2) {
        if(pair[pointChild][nextChild(child,pointChild+1)] == 1) {
            //printf("finalPair: %d %d\n", pointChild, nextChild(child,pointChild+1));
            (*numPair)++;
        }
    }
    else {
        for(int i=pointChild+1; i<n; i++) {
            if(pair[pointChild][i] == 1 && child[i]==1) { //if there is a pair with pointChild
                child[pointChild]=0, child[i]=0;
                //printf("Pair:%d %d\n", pointChild, i);
                makePair(child, leftChild-2, numPair);
                child[pointChild]=1; child[i]=1;
            }
        }
    }
    
}
 
int main () {
    
    int numPair=0;
    int child[maxN];
    int temp1, temp2;
    
    scanf("%d", &c);
    
    for(int i = 0; i < c; i++) {
        scanf("%d %d", &n, &m);
        initPair();
        for(int j = 0; j < m; j++) {
            scanf("%d %d", &temp1, &temp2);
            pair[temp1][temp2]=1, pair[temp2][temp1]=1;
        }
        
        for(int j=0; j<n; j++) child[j]=1;
        
        numPair = 0;
        makePair(child, n, &numPair);
        printf("%d\n", numPair);
    }
}

내 방법은 완전탐색을 하되, 수형도처럼 진행한다.

 

 

예를 들어 학생 A, B, C, D, E, F가 있다고 하면

A(pointChild)와 B가 친구인지 확인한 후(line 33), 친구이면 다음 학생으로 넘어간다.(nextChild)

A와 B는 이미 짝지어져 있으므로(child[i]==0) C로 넘어가서 C와 D가 친구인지 확인한다. 만약 친구가 아니라면 C와 E가 친구인지 확인한다.

그러다 남은 학생이 2명이고, 둘이 친구라면, pair의 개수를 1개 카운트하고 리턴한다.(line 28)

 

 

nextChild()에서 더 빠르게 찾는 방법이 있을 것 같지만 n이 매우 작으므로 그냥 진행하였다.