[Algospot] PICNIC (경우의 수, 탐색)

#. 문제 

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

* 이 문제의 저작권은 Algospot에 있습니다.

[ 문제 ]

안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다.

각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 봅니다. 예를 들어 다음 두 가지 방법은 서로 다른 방법입니다.

(태연,제시카) (써니,티파니) (효연,유리)

(태연,제시카) (써니,유리) (효연,티파니)

[ 입력 ]

입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 학생의 수 n (2 <= n <= 10) 과 친구 쌍의 수 m (0 <= m <= n*(n-1)/2) 이 주어집니다. 그 다음 줄에 m개의 정수 쌍으로 서로 친구인 두 학생의 번호가 주어집니다. 번호는 모두 0 부터 n-1 사이의 정수이고, 같은 쌍은 입력에 두 번 주어지지 않습니다. 학생들의 수는 짝수입니다.

[ 출력 ]

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

#. 문제 해결 과정

  1. 문제를 읽고 이해하기

  2. 문제를 익숙한 용어로 재정의 + 추상화

    - 항상 서로 친구인 학생들끼리만 짝을 지어주기

    - 학생들을 짝지어줄 수 있는 방법의 수를 계산

    - 조건 : TestCast C <= 50

              학생의 수 n (2 <= n <= 10), 친구 쌍의 수 m (0 <= m <= n(n-1)/2)

  3. 어떻게 해결할지 계획 세우기(알고리즘, 자료구조 선택) -> 풀이

  4. 계획 검증하기(수행 시간과 사용 메모리 확인)

    - 시간 제한 : 1000ms(1c) / 메모리 : 65536kb(64MB)

    - 답의 수 예측 : 가장 많은 답을 가질 수 있는 입력은 10명의 학생이 모두 서로 친구인 경우,

      이때 가장 번호가 빠른 학생이 선택할 수 있는 짝은 9명, 그 다음 학생이 선택할 수 있는 짝은 7명,

      최종 답의 개수 = 9 x 7 x 5 x 3 x 1 = 945

  5. 계획 수행하기

  6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아보기

#. 풀이

  1. 테스트 케이스 수 입력

  2. 학생 수(N), 친구 쌍의 수(M) 입력

  3. M개의 쌍으로 이루어진 서로 친구인 학생의 번호 입력

  4. N명의 학생을 친구끼리만 짝지어줄 수 있는 방법의 수 출력

    - countPairings() 함수에서 함수를 통해 경우의 수를 탐색

    - 기저 사례

        ㄴ 남은 학생들 중 가장 번호가 빠른 학생을 선택 (중복 방지)

        ㄴ 모든 학생이 짝을 찾으면 한 가지 방법을 찾았으니 종료

        ㄴ 서로 짝도 없고, 친구 관계일 경우 -> 재귀 호출

#. 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class C64 {
    static int C;
    static int N;
    static int M;
    static boolean areFriend[][];
    
    public static void Picnic() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        // 1. 테스트 케이스 입력
        C = Integer.parseInt(br.readLine());
        assert C < 50 : "Error :: C(testCase) <= 50";
        
        for(int tc=0; tc<C; tc++) {
            // 2. N(학생 수)과 M(친구 쌍의 수) 입력
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());  // 학생의 수
            M = Integer.parseInt(st.nextToken());  // 친구 쌍의 수
            assert N>2 | N<10 | M>0 | M<((N*(N-1))/2) : "Error :: 2 <= N <= 10, 0 <= M <= n(n-1)/2";
            
            // 3. M개의 쌍으로 이루어진 서로 친구인 학생들의 번호를 friend 배열에 저장
            areFriend = new boolean[N][N];
            StringTokenizer frd = new StringTokenizer(br.readLine());
            while(frd.hasMoreTokens()) {
                int f1 = Integer.parseInt(frd.nextToken());
                int f2 = Integer.parseInt(frd.nextToken());
                assert f1>=0 | f1<N | f2>=0 | f2<N : "Error :: 0 <= number < N";
                areFriend[f1][f2] = areFriend[f2][f1] = true;
            }
            
            // 4. N명의 학생을 친구끼리만 짝지어줄 수 있는 방법의 수 출력
            boolean[] bePaired = new boolean[N];
            bw.write(String.format("%d\n", countPairings(bePaired)));
        }    
        bw.close();
    }
    
    public static int countPairings(boolean[] bePaired) {
        // 기저 사례 1. 남은 학생들 중 가장 번호가 빠른 학생 선택(중복 방지)
        int fastNum = -1;
        for(int i=0; i<N; i++) {
            if(!bePaired[i]) {
                fastNum = i;
                break;
            }
        }
        // 기저 사례 2. 모든 학생이 짝을 찾으면 한 가지 방법을 찾았으니 종료
        if(fastNum == -1) return 1;
        // 기저 사례 3. 서로 짝도 없고, 친구 관계일 경우 재귀 호출을 사용
        int ret = 0;
        for(int w=fastNum+1; w<N; w++) {
            if(!bePaired[w] & areFriend[fastNum][w]) {    // areFriend == TRUE 로 짝이 없고, 친구 관계일 경우
                bePaired[fastNum] = bePaired[w] = true;
                ret += countPairings(bePaired);
                bePaired[fastNum] = bePaired[w] = false;
            }
        }
        return ret;
    }
    
    public static void main(String[] args) throws Exception {
        C64.Picnic();
    }
}
 

#. 결과

  - Input --------------------------------------------------------

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

------------------------------------------------------------------

  - Output --------------------------------------------------------

1

3

4

------------------------------------------------------------------