소풍 (문제 ID: PICNIC, 난이도: 하)

전체 입력의 첫줄에는 테스트 케이스의 수 C 가 주어집니다.

 

각 케이스의 첫 줄에는 학생의 수 n 과 친구 쌍의 수 m 이 주어집니다.

각 케이스의 2 번째 줄에는 m개의 정수 쌍으로 서로 친구인 두 학생의 번호가 주어집니다. 

번호는 모두 0부터 n-1 사이의 정수이고, 같은 쌍은 입력에 두 번 주어지지 않습니다.

학생들의 수는 짝수 입니다.

 

출력

각 테스트 케이스마다 한 줄에 모든 학생을 친구끼리만 짝지어줄 수 있는 방법의 수를 출력합니다.

 

 

 

public class SoPoong {
    public static void main(String[] args) {
        String[] inputStrs = new String[]{
                "3" // 총 테스트 케이스는 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"
        };

        solution(inputStrs);
    }

    public static int solution(String[] inputStrs) {
        int totalCase = Integer.parseInt(inputStrs[0]);

        for(int i=0; i < totalCase ; i++) {
            int peopleCount = Integer.parseInt(inputStrs[i*2+1].split(" ")[0]);
            int pairCount = Integer.parseInt(inputStrs[i*2+1].split(" ")[1]);
            PairCounter pairCounter = new PairCounter(peopleCount, pairCount);
            pairCounter.setUpFriends(inputStrs[i*2+2].split(" "));
            boolean[] taken = new boolean[peopleCount];
            System.out.println(pairCounter.countPairings(taken));
        }

        return 0;
    }

    public static class PairCounter {
        public int peopleCount;
        public int pairCount;

        private boolean[][] areFriends;

        public PairCounter(int peopleCount, int pairCount) {
            this.peopleCount = peopleCount;
            this.pairCount = pairCount;

            areFriends = new boolean[peopleCount][peopleCount];
            System.out.println("peopleCount : " + peopleCount);
            System.out.println("pairCount : " + pairCount);
        }

        public void setUpFriends(String[] args) {
            for(int i=0; i < args.length; i+=2) {
                int person1 = Integer.parseInt(args[i]);
                int person2 = Integer.parseInt(args[i+1]);
                areFriends[person1][person2] = areFriends[person2][person1] = true;
            }
        }

        public int countPairings(boolean[] taken) {
            int firstFree = -1;
            for(int i=0; i<peopleCount; i++) {
                if(!taken[i]) {
                    firstFree = i;
                    break;
                }
            }

            if(firstFree == -1) {
                return 1;
            }

            int ret = 0;
            for(int pairWith = firstFree+1; pairWith<peopleCount; pairWith++) {
                if(!taken[pairWith] && areFriends[firstFree][pairWith]) {
                    taken[firstFree] = taken[pairWith] = true;
                    int cnt =  countPairings(taken);
                    ret += cnt;
                    taken[firstFree] = taken[pairWith] = false;
                }
            }
            return ret;
        }
    }

}