문제 풀이 - 소풍(JAVA)

소풍

문제의 분할

여기서 해결해야 할 문제는 '아직 짝을 찾지 못한 학생들의 명단이 주어질 때 친구끼리 둘씩 짝짓는 경우의 수를 계산하라'입니다. 경우의 수를 반환하는 int countPairings(boolean taken[10]) 함수를 만들면 됩니다. 이 함수를 호출하면 짝을 찾아야 하는 학생은 그 학생보다 뒤에 있는 학생들과 차례차례 짝을 지어주고 명단에서 제외 후 재귀 호출을 합니다.

기저 사례의 선택

모든 학생들이 짝이 있다면 한 가지 방법을 찾았으므로 1을 반환합니다.

시간 복잡도 분석

이 문제에서 가장 많은 답을 가질 수 있는 입력은 열 명의 학생이 모두 서로 친구인 경우입니다. 이때 가장 번호가 빠른 학생이 선택할 수 있는 짝은 아홉 명이고, 그 다음학생이 선택할 수 있는 짝은 일곱 명입니다. 따라서 가장 오래 걸리는 경우의 수는 $9*7*5*3*1=945$입니다.

구현

import java.util.*;

public class Main {

    // 학생의 수
    public static int n;
    // 친구 쌍의 수
    public static int m;
    // 친구인지 아닌지 저장한 배열
    public static boolean[][] areFriends;
    // 짝이 지어졌는지 여부를 저장하는 배열
    public static boolean[] paired;
    // 문제의 답
    public static int result;

    // 입력값을 받는 함수입니다.
    public static void input(Scanner scanner) {
        n = scanner.nextInt();
        areFriends = new boolean[n][n];
        paired = new boolean[n];
        m = scanner.nextInt();

        for (int i = 0; i < m; i++) {
            int friend1 = scanner.nextInt();
            int friend2 = scanner.nextInt();
            areFriends[friend1][friend2] = true;
            areFriends[friend2][friend1] = true;
        }
    }

    // 문제를 해결하는 함수입니다.
    public static void solve() {
        result = countPairings(paired);
    }

    // 아직 짝을 찾지 못한 학생들의 명단이 주어질 때 친구끼리 둘씩 짝짓는 경우의 수를 계산하는 함수입니다.
    public static int countPairings(boolean[] taken) {
        // 남은 학생들 중 가장 번호가 빠른 학생을 찾습니다.
        int firstFree = -1;
        for (int i = 0; i < n; i++) {
            if (!taken[i]) {
                firstFree = i;
                break;
            }
        }
        // 기저 사례: 모든 학생들이 짝이 있다면 한 가지 방법을 찾았으므로 1을 반환합니다.
        if (firstFree == -1) return 1;
        int result = 0;
        // 이 학생보다 뒤에 있는 학생들을 차례차례 짝을 짓습니다.
        for (int pairWith = firstFree + 1; pairWith < n; pairWith++) {
            if (!taken[pairWith] && areFriends[firstFree][pairWith]) {
                taken[firstFree] = taken[pairWith] = true;
                result += countPairings(taken);
                taken[firstFree] = taken[pairWith] = false;
            }
        }
        return result;
    }

    // 답을 출력하는 함수입니다.
    public static void output() {
        System.out.println(result);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();
        for (int i = 0; i < testCase; i++) {
            input(scanner);
            solve();
            output();
        }
    }
}

회고