[알고스팟] PICNIC

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

algospot.com :: PICNIC

 

---

 

 

알고리즘

학생들을 짝지어 주되, 짝이 된 학생끼리는 서로 친구이도록 짝을 지어줘야하는 문제이다.

친구인지 아닌지 여부는 미리 주어진다.

 

학생의 수가 총 4명이고 n = 4,

친구쌍이 총 6쌍이고 다음과 같을 때 m = 6

(0,1) (1,2) (2,3) (3,0) (0,2) (1,3)가 서로 친구인 쌍이다.

4 6 
0 1 1 2 2 3 3 0 0 2 1 3 

 

0번 학생부터 4번 학생까지 완전탐색으로 짝을 지어준다. 

이때 중요한 점은, 자기번호보다 번호가 큰 학생들 중에 친구인 학생과 짝을 지어준다.

 

k번 학생의 짝을 지어줄 차례일때 k보다 번호가 큰 학생들 중에 k번 학생과 친구인 학생을 찾아서 짝을 지어줘야 한다.

(0,1) 이나 (1,0)이나 결국 같은 케이스이기 때문에 중복을 피하기 위해 오름차순대로 짝을 맺어주는 것이다.

 

 

 

코드 설명

• int isPair[a][b] 배열 

a번 학생과 b번 학생이 서로 친구이면 isPair[a][b] = isPair[b][a] = true 이고,

서로 친구가 아니면 isPair[a][b] = isPair[b][a] = false 이다.

        for(int j=0;j<m;j++){
            int a,b;
            scanf("%d %d",&a,&b);
            isPair[a][b]=isPair[b][a]=1;
        }

 

 

• int child[n] 배열 

k번 학생이 짝을 지었을 때, 친구과 짝을 이루었으면 child[k] = true, 그렇지 않으면 child[k] = false (0<= k < n)

오름차순이므로 k번 이후의 학생들(k<i<n) 중 k번 학생과 친구이면서(isPair[k][i]=true) 아직 짝이 되지 못한 학생(child[i]=false)을 찾아서 짝을 만들어준다.

    for(int i=k+1;i<n;i++){
        if(isPair[k][i] && !child[i]){
            child[i]=child[k]=1;
            makePair(isPair, child,k+1);
            child[i]=child[k]=0;
        }
    }

 

 

 

오름차순 번호 순대로 짝을 지어주다가 k번 학생 차례가 됐다.

그런데 k번 학생이 자기보다 앞의 번호를 가진 학생 누군가와 이미 짝이 되어있는 상태라면? 즉, child[k] = true라면?

이미 짝이 되어있으므로 또 짝을 찾아줄 필요가 없다. 따라서, 이때는 본인은 pass하고, 다음(k+1번) 학생이 짝을 찾도록 넘겨준다.

   if(child[k]){
        makePair(isPair, child,k+1);
        return;
    }

 

 

 

base case. 

탐색은 0번부터 n-1번까지 오름차순 번호대로 진행된다. 따라서 n-1번 학생 차례일때는 자기보다 높은 번호가 없으니까 더 이상 짝을 지어줄 수 없다.(결국 이 상황에서 n-1번 학생은 이미 다른 학생과 짝이 지어진 상태여야 한다는 걸 알수 있다.)

    if(k==n-1){
        for(int i=0;i<n;i++){
            if(!child[i]){
                return;
            }
        }
        count++;
        
        return;
    }

마지막 n-1번 학생까지 탐색했을때, 0~n-1번 중 한명이라도 child[k] = false (0<=k<n)가 존재하면 문제의 조건(항상 서로 친구인 학생들끼리만 짝이 되는 경우의 수)에 만족하지 못하므로 카운트를 하지 않는다.

반면, child 배열이 모두 true인 경우, 0~4번 학생 모두 친구인 학생과 짝이 된 것이므로 카운트를 해준다.

 

 

 

재귀함수를 통해 모든 탐색을 진행한 후, 최종적으로 count 변수에 남아있는 값이 항상 서로 친구인 학생끼리 짝이 되는 모든 경우의 수가 된다.

 

 

전체코드 : 

#include <stdio.h>
int count;
int C,n,m;
void makePair(int isPair[10][10], int child[10], int idx);
int main(int argc, const char * argv[]) {
    
    scanf("%d",&C);
    
    for(int i=0;i<C;i++){
        count=0;
        int isPair[10][10]={{0}};
        int child[10]={0};
        
        scanf("%d %d",&n,&m);
        
        for(int j=0;j<m;j++){
            int a,b;
            scanf("%d %d",&a,&b);
            isPair[a][b]=isPair[b][a]=1;
        }
        
        makePair(isPair,child,0);
        printf("%d\n",count);
    }
    
    return 0;
}
void makePair(int isPair[10][10], int child[10], int k){
    
    if(k==n-1){
        for(int i=0;i<n;i++){
            if(!child[i]){
                return;
            }
        }
        count++;
        
        return;
    }
    
    if(child[k]){
        makePair(isPair, child,k+1);
        return;
    }
    
    for(int i=k+1;i<n;i++){
        if(isPair[k][i] && !child[i]){
            child[i]=child[k]=1;
            makePair(isPair, child,k+1);
            child[i]=child[k]=0;
        }
    }
    
    return;
}