[알고스팟] 소풍 :: 늦깎이 IT

[알고스팟 소풍 URL]

완전 탐색 문제입니다.

1. 아직 짝을 이루지 못한 기준 학생을 찾는다. 학생을 찾을 때에는 맨 앞쪽의 학생부터 찾는다.

 - (0, 1) 학생과 (1, 0) 학생이 짝을 이루는 경우는 같은 상황이기 때문에, 중복을 피해야 한다.

2. 짝을 이루지 못한 기준이 되는 학생을 찾았으면, 그 학생과 짝을 이룰 다른 학생을 찾는다.

3. 두 명의 학생이 짝을 이뤘으면, count(짝을 이룬 학생 수)를 2 증가시켜 다시 DFS 탐색을 시작한다.

[소스코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int C, N, M, ans;
    public static boolean[][] students;
    public static boolean[] visited;
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        C = Integer.parseInt(br.readLine());
 
        for (int tCase = 1; tCase <= C; tCase++) {
 
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
 
            ans = 0;
            students = new boolean[N][N];
            visited = new boolean[N];
 
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < M * 2; i += 2) {
                int st1 = Integer.parseInt(st.nextToken());
                int st2 = Integer.parseInt(st.nextToken());
                students[st1][st2] = students[st2][st1] = true;
            }
            countPair(0);
            System.out.println(ans);
        }
    }
 
    public static void countPair(int count) {
 
        if (count == N) {
            ans += 1;
            return;
        }
 
        int firstStudent = -1;
        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                firstStudent = i;
                break;
            }
        }
 
        for (int i = firstStudent + 1; i < N; i++) {
            if (!visited[i] && students[i][firstStudent]) {
                visited[i] = visited[firstStudent] = true;
                countPair(count + 2);
                visited[i] = visited[firstStudent] = false;
            }
        }
    }
}