[Algospot] 알고스팟 PICNIC 소풍

출처:  https://algospot.com/judge/problem/read/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

 

[두번째 Test Case]

N = 4 → [0, 1, 2, 3]

▶ 친구가 가능한 쌍: (0, 1) (1, 2) (2, 3) (3, 0) (0, 2) (1, 3)

주의해야할 경우는 [(0 1) (2 3)] = [(1 0) (2 3)] = [(0 1) (3 2)] = [(1 0) (3 2)]로 모두 같습니다.

ex) (0, 1)을 선택한 경우, 남은 숫자 중 가장 낮은 숫자 2 선택하고 선택되지 않은 숫자 3을 선택

 

[코드 해석]

『 0 』에서 부터 친구가 가능한 쌍만을 찾아갑니다.

▷ (0, 1) → 1은 이미 선택되었음 → (2, 3) → 3은 이미 선택되었음

▷ (0, 2) → (1, 3) → 2는 이미 선택되었음 → 3은 이미 선택되었음

▷ (0, 3) → (1, 2) → 2는 이미 선택되었음 → 3은 이미 선택되었음

※ 『 1 』 , 『 2 』, 『 3 』에서 시작하는 탐색은 for문 순서상 『 0 』을 선택할 수 없으므로 count X

    (1, 0), (2, 0), (3, 0)과 같이 중복 선택을 방지하기 위함.

---

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
 
int n, m, answer;
vector<int> check;
bool areFriends[10][10];
 
void countPairings(int idx) {
    if (idx == n) {
        answer++;
        return;
    }
 
    // 이미 선택된 경우
    if (check[idx]) {
        countPairings(idx + 1); 
        return;
    }
 
    // 가까운 숫자 부터 확인
    for (int j=idx+1; j < n; j++) {
        // 선택되지 않은 숫자이면서 친구가 가능한 숫자
        if (!check[j] && areFriends[idx][j]){
            check[j] = true; // 짝 설정
            countPairings(idx+1);
            check[j] = false; // 다음 경우의 수를 알아보기 위해 해제
        }
    }
}
 
int main() {
    int C;
    cin >> C;
 
    while (C--) {
        cin >> n >> m;
 
        check = vector<int>(n, false);
        memset(areFriends, false, sizeof(areFriends));
        answer = 0;
 
        int a, b; // 가능한 친구 쌍
        for (int i = 0; i < m; i++) {
            cin >> a >> b;
            areFriends[a][b] = areFriends[b][a] = true;
        }
 
        countPairings(0);
        cout << answer << endl;
    }
    return 0;
}