6.3 소풍

6.3 소풍

제출일 : 2021-01-03

문제 풀이 시간 : 30M

---

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

문제

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

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

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

입력

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

출력

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

예제

입력

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

문제 풀이 접근

가능한 경우의 수를 재귀함수를 이용하여 구현하였습니다.

A라는 변수를 통해 짝이 맞춰지지 않은 가장 빠른 번호의 학생을 구하고 A번 학생과 짝이 가능하다면 짝을 지어주고 재귀함수를 호출하여 문제를 해결하였습니다.

처음 문제를 읽고 가능한 모든 경우의 수를 파악한 뒤 요구조건에 만족한다면 카운트 하는 방식으로 문제를 해결하려 했습니다. 아래의 소스코드보다 더 많은 변수들이 필요했고 중복을 제거하기 위해 같은 경우지만 다른 경우로 카운트 (1122 == 2211)되는 경우를 제거 해주어야 했습니다. 소스코드가 점점 길어지고 지저분해져 아래와 같이 가능한 경우만 계속 재귀함수를 호출할 수 있도록 코딩하였습니다.

코드

언어 : JAVA

실행 시간 : 176ms

import java.util.Scanner;

public class Main {
    static int N, M, ans;
    static boolean[] visit;
    static int[][] map;

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

        int T = sc.nextInt();
        for (int tc = 0; tc < T; tc++) {
            N = sc.nextInt();
            M = sc.nextInt();

            map = new int[N][N];
            for (int i = 0; i < M; i++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                map[a][b] = map[b][a] = 1;
            }

            ans = 0;
            visit = new boolean[N];
            solve();
            System.out.println(ans);
        }
    }

    private static void solve() {
        int A = -1;
        for (int i = 0; i < N; i++) {
            if (!visit[i]) {
                A = i;
                break;
            }
        }

        if (A == -1) {
            ans++;
            return;
        }

        for (int i = A + 1; i < N; i++) {
            if (!visit[i] && map[A][i] == 1) {
                visit[A] = visit[i] = true;
                solve();
                visit[A] = visit[i] = false;
            }
        }
    }

}