문제 ID : PICNIC, 난이도: 하

 

picnic 소풍

 

항상 친구인 학생들 끼리만 짝을 지어주는 프로그램

/*

    테스트 케이스 : C

    학생 수  : N

    학생 짝의 수 : M

    서로 친구인 학생 쌍이 주어진다.

*/

#include <iostream>
using namespace std;
 
int dfs(int taken[11]);
int dfs2(int taken[11]);
 
int taken[11] = {0,};
int checkFriend[11][11] = {0,};
int C,N,M = 0;
int main(){
    cin >> C;
    for(int i = 0; i < C; i ++){//test case 3번
        cin >> N >> M;
        for(int j = 0; j < M; j ++){
            int friend1, friend2;
            cin >> friend1 >> friend2;
        // (1, 2) 와 (2, 1)은 같은 의미이다.(둘이 친구라는 뜻이기 때문에) 
            checkFriend[friend1][friend2] = 1;
            checkFriend[friend2][friend1] = 1;
        }
    }
    int ret = dfs2(taken);
    cout << "ret : "<< ret;
}
 
 

메인함수에서는 위와 같이 입력을 받아서 dfs를 실행하기 위한 조건을 세팅한다.

int dfs(int taken[11]){
    bool finished = true;
    for(int i = 0; i < N; i ++){
    if(!taken[i]) finished = false;
    }    
    if(finished) return 1;
    
    int ret = 0;
    for(int i = 0; i < N; i ++){
        for(int j = 0; j < N; j ++){
            if(!taken[i] && !taken[j] && checkFriend[i][j]){
                taken[i] = taken[j] = true;
                ret += dfs(taken);
                taken[i] = taken[j] = false;
            }  
        }
    }
    return ret;
}

int dfs2(int taken[11]){
    int firstFree = -1;
 
    for(int i = 0; i < N; i ++){
        if(!taken[i]) firstFree = i;
        break;
    }    
    if(fristFree == -1) return 1;
 
    int ret = 0;
    for(int pairWith = firstFree + 1; pairWith < N; pairWith ++){
        if(!taken[pairWith] && checkFriend[firstFree][pairWith]){
           taken[firstFree] = taken[pairWith] = true;
            ret += dfs2(taken);
           taken[firstFree] = taken[pairWith] = false;
        }
    }
    return ret;
}