소풍 문제

1. 문제 설명

(1) 소풍 문제는 학생들을 두 명씩 짝 지어 목록을 만드는 것이다.

( 단, 항상 서로가 친구인 학생들끼리만 짞을 지어야 한다. )

(2) 최대한 구할 수 있는 모든 경우의 수를 만들어보자.

( 예) (a,b) (c,d) (e,f)와 (a,b) (c,e) (d,f)는 서로 다른 방법이다. )

 

 

 

2. 입출력 조건 및 예제

입력 조건

(1) 첫 번째 줄에는 총 입력 받을 소풍 문제 개수를 입력받는다.

 

(2) 두 번째 줄부터는 학생의 수 N과 친구의 쌍의 수 M을 입력 받는다.

( N >= 2 && N <= 10 ) ( M >= 0 && M <= N(N-1)/2 )

 

(3) 세 번째 줄부터는 서로가 친구인 목록을 적는다.

 

출력 조건

(1) 구할 수 있는 모든 경우의 수를 출력한다.

 

입력 예제

3
2 1
0 1
4 6
0 1 1 2 2 3 3 0 0 2 1 3
6 10
0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5

출력 예제

1
3
4

 

 

 

3. 기저 사례

(1) 모든 학생의 짝을 찾았다면

 

 

 

4. 코드

public class PICNIC {
    // 각각 학생의 수, 친구의 쌍의 수, 서로 친구인지 확인하는 변수
    static int N, M;
    static boolean[][] isFriend;
    
    static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    
    public static void main(String[] args) throws Exception {
        int C = Integer.parseInt(sc.readLine());
        
        for(int i=0; i<C; i++){
            st = new StringTokenizer(sc.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            
            // 서로 친구인지 아닌지 확인하는 isFriend 변수에
            // 입력값을 저장한다.
            isFriend = new boolean[N][N];
            int[] A = new int[M*2];
            st = new StringTokenizer(sc.readLine());
            for(int k=0; k<M*2; k++) {
                A[k] = Integer.parseInt(st.nextToken());
                if(k%2==1) isFriend[A[k-1]][A[k]] = isFriend[A[k]][A[k-1]] = true;
            }
            sb.append(countPairings(new boolean[N])+"\n");
        }
        System.out.println(sb);
    }
    
    static int countPairings(boolean[] stu) {
        int ret=0, idx=-1;
        
        // 만약 짝이 없는 경우, idx에 학생 인덱스 위치를 저장한다.
        for(int i=0; i<N; i++) {
            if(!stu[i]) {
                idx=i;
                break;
            }
        }
        
        // 모든 학생이 짝을 이루었을 때
        // 하나의 경우의 수로 체크한다.
        if(idx==-1) return 1;
        
        // 짝을 짓지 못한 idx 위치에 있는 학생을 N만큼 짝을 이루도록 반복/재귀한다.
        for(int pairWith=idx+1; pairWith<N; pairWith++) {
            if(!stu[pairWith] && isFriend[idx][pairWith]) {
                stu[idx]=stu[pairWith]=true;
                ret += countPairings(stu);
                stu[idx]=stu[pairWith]=false;
            }
        }
        return ret;
    }
}