[Java] 알고스팟 : PICNIC

문제 링크

1.

종만북 초반 4장까지 개념만 보면서 지루했었는데, 드디어 문제 풀이에 들어갔다.

근데 난이도 '하'인데 뭐가 이렇게 어렵지..

종만북 완독 가능할지 모르겠다.

 

완전 탐색 기법을 재귀적으로 풀어보라는 문제여서 그렇게 풀어보려고 노력했다.

그런데, 잘 떠오르지 않아 나만의 방식으로 조합 등을 써서 풀어보려고 했으나, 풀지 못했다.

 

2.

자세한 풀이는 책 참고 (p.157)

 

• 각 답을 만드는 과정을 여러 개의 조각으로 나누기.
• 서로 친구인 배열을 만드고 거기서 친구인 두 학생을 찾아 짝짓고, 남은 학생들을 짝짓자.
• 중복 체크!

 

3.

import java.util.Scanner;

public class PICNIC {
    static int n, m;
    static boolean[][] areFriends;

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

        int C = sc.nextInt();
        for (int k = 0; k < C; k++) {
            n = sc.nextInt();
            m = sc.nextInt();
            areFriends = new boolean[n][n];
            boolean[] checked = new boolean[n];

            for (int i = 0; i < m; i++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                areFriends[a][b] = true;
                areFriends[b][a] = true;
            }
            System.out.println(solution(checked));
        }
        sc.close();
    }

    static int solution(boolean[] checked) {
        int firstFree = -1;
        for (int i = 0; i < n; i++) {
            if (!checked[i]) {
                firstFree = i;
                break;
            }
        }
        if (firstFree == -1) {
            return 1;
        }
        int cnt = 0;
        for (int i = firstFree + 1; i < n; i++) {
            if (!checked[i] && areFriends[firstFree][i]) {
                checked[firstFree] = checked[i] = true;
                cnt += solution(checked);
                checked[firstFree] = checked[i] = false;
            }
        }
        return cnt;
    }
}

 

 

4.

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략 (구종만)