소풍 - Brute Force

Brute Force 시 같은 답을 중복으로 세는 상황이 발생할 수 있다 이를 해결하기 위해서는 항상 특정 형태를 갖는 답만을 세는 것이다. 흔히 사용하는 방법으로는 같은 답 중에서 사전 순으로 가장 먼저 오는 답 하나만을 센다. 예를 들어 (1,0),(2,3)이나 (2,3),(0,1)은 세지 않지만 (0,1),(2,3)은 센다. 이렇게 하기 위해서 각 단계에서 남아 있는 학생들 중 가장 번호가 빠른 학생의 짝을 찾아주면 같은 답 중 사전 순으로 먼저 오는 답만을 셀 수 있다.

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int testCase = 0;
        testCase=Integer.parseInt(st.nextToken());

        for(int t=0; t<testCase; t++) {
            int n,m;
            boolean[][] pairs;
            boolean[] taken;
            st = new StringTokenizer(br.readLine()," ");
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            taken = new boolean[n];
            pairs = new boolean[n][n];

            st = new StringTokenizer(br.readLine()," ");
            for(int i=0; i<m; i++) {
                int first = Integer.parseInt(st.nextToken());
                int second = Integer.parseInt(st.nextToken());
                pairs[first][second] = true;
                pairs[second][first] = true;
            }
            int answer = f(taken, pairs);
            System.out.print(answer);
            System.out.print(" ");
        }
    }
    static int f(boolean[] taken, boolean[][] pairs) {
        int firstFree = -1;

        //남은 학생들 중 가장 번호가 빠른 학생을 찾는다.
        for(int i=0; i<taken.length; i++) {
            if(!taken[i]) {
                firstFree = i;
                break;
            }
        }

        if(firstFree == -1) return 1;
        int ret = 0;
        //이 학생과 짝지을 학생을 결정한다.
        for(int i=firstFree+1; i<taken.length; i++) {
            if(!taken[i] && pairs[firstFree][i]) {
                taken[firstFree] = taken[i] = true;
                ret += f(taken, pairs);
                taken[firstFree] = taken[i] = false;
            }
        }
        return ret;
    }
}