알고리즘 문제 해결 PICNIC

짝이 될 수 있는 모든 경우의 수를 구하는 문제

4 6

0 1 1 2 2 3 3 0 0 2 1 3 이 경우에는

{0,1} {1,2} {2,3} {3,0} {0,2} {1,3} 0,1을 고른 상태에서 나머지 쌍들을 → 방향으로 확인 하는 것이다.

1,2는 앞서 고른 1과 중복이 되서 패스, 2,3 은 선택 할 수있다. 그러면 다시 2,3, 제외하고 그 뒤로 연결되는게 있는지 확인을 한다.

그렇게 0,1을 기준으로 확인이 다 끝났으면 그 다음 1,2 또 끝나면 2,3 이렇게 확인 하는 것이다.

이 문제의 base 기준은

1.모든 학생들이 짝을 이루었을 때 → 1

2.다 확인을 했는데 결국에는 짝을 이루지 못했을때 → 0

recuersive는

0 기준이 될 때 1~5까지 확인

1 기준이 될 때 2~5 확인

2 기준이 될 때 3~5 이렇게

i가 선택이 될 때 i+1을 확인 한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int [][] arr;
    static int n,m,C,Answer;
    static boolean [] flag;
    public static int search(boolean [] flag,int [][] arr){
        int index1 = -1;
        for(int i=0; i<n; i++){
            if(!flag[i]){
                index1 = i;
                break;
            }
        }
        if(index1 == -1){
            return 1;
        }
        int ret = 0;
        for(int index2 = index1+1; index2< n; index2++){
            if((!flag[index2])&&arr[index1][index2]==1){
                flag[index2] = true;
                flag[index1] = true;
                ret += search(flag,arr);
                flag[index2] = false;
                flag[index1] = false;
            }
        }
        return ret;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb =new StringBuilder();
        C = Integer.parseInt(st.nextToken());
        for(int i=0; i<C; i++){
            st = new StringTokenizer(br.readLine());
            n= Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());

            arr =new int [n][n];
            flag = new boolean[n];
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++){ //쌍의 반복을 진행 하게 될 것
                int par1 = Integer.parseInt(st.nextToken());
                int par2 = Integer.parseInt(st.nextToken());

                arr[par1][par2] = 1;
                arr[par2][par1] = 1;
            }
            sb.append(search(flag,arr));
            sb.append("\n");
        }
        System.out.println(sb);
    }
}