[PICNIC] 소풍

문제 주소

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

예제 입력

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

깃허브 주소

https://github.com/SeungHwan-Choi/Algorithm/blob/master/src/bruteforce/Picnic.java

package bruteforce;

import java.util.Scanner;

public class Main {

    // 친구 관계를 담고 있는 변수
    private static boolean[][] areFriends;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int loop = sc.nextInt();

        // 짝이 맞춰졌는지 확인하는 변수
        boolean[] paired;
        int[] result = new int[loop];

        while (loop-- > 0) {
            // [학생 수, 친구 쌍 의 수]
            int cntStudents = sc.nextInt();
            int cntFriends = sc.nextInt();

            // 학생 수로 초기화
            paired = new boolean[cntStudents];
            areFriends = new boolean[cntStudents][cntStudents];

            // 친구 관계 여부 삽입.
            for (int i = 0; i < cntFriends; i++) {
                areFriends[sc.nextInt()][sc.nextInt()] = true;
            }

            result[loop] = countParings(paired);
        }

        for (int i = result.length - 1; i >= 0; i--) {
            System.out.println(result[i]);
        }
    }

    private static int countParings(boolean[] paired) {

        // 학생 수
        int cntStudents = paired.length;
        // 짝이 지어지지 않은 학생 중 가장 빠른 번호의 학생을 담을 변수.
        int remainFirst = -1;

        // 짝이 맞춰지지 않은 학생중 출석번호가 가장 빠른 학생을 찾는다.
        for (int i = 0; i < cntStudents; i++) {
            if (!paired[i]) {
                remainFirst = i;
                break;
            }
        }

        // 모든 학생이 짝이 맞춰졌다면 짝을 맞추는 하나의 경우를 만족했으므로 1을 반환한다.
        if (remainFirst == -1) {
            return 1;
        }

        // 경우의 수를 반환할 변수
        int returnResult = 0;

        // #1.countParings 메소드로 짝 맞추기의 기준이 되는 학생을 선택한다.
        // #2.for문으로 기준이 되는 학생의 '친구'를 골라 한쌍으로 만든다.
        // #3.위의 한쌍을 제외한 가장 빠른 출석번호의 학생을 찾아 반복한다.(첫번째 재귀 함수 실행중)
        // #4.모든 학생이 짝 맞추기가 완료되면 하나의 경우를 만족했으므로 1을 반환한다.
        // #5.처음으로 돌아와 for문으로 #1 학생의 다음 친구를 찾는다.
        // #6 1-5를 반복한다.
        for (int friend = remainFirst + 1; friend < cntStudents; friend++) {
            if (!paired[friend] && areFriends[remainFirst][friend]) {
                paired[remainFirst] = paired[friend] = true;
                returnResult += countParings(paired);
                paired[remainFirst] = paired[friend] = false;
            }
        }
        return returnResult;
    }
}

자바로 알고리즘 문제풀이를 준비하는 목적으로 '알고리즘 문제 해결 전략'을 분석하여 공부하고 있다. 추후 잊어버리지 않도록 정리한다.