6장 무식하게 풀기

6.3 문제: 소풍 (문제ID: PICNIC, 난이도: 하)

문제 자세히 보기

#include <iostream>

using namespace std;

int pairing(bool friends[10][10], bool students[10], const int n) {
    int firstFree = -1;
    for (int i = 0; i < n; ++i) {
        if (students[i]) {
            firstFree = i;
            break;
        }
    }
    if (firstFree == -1) return 1;

    int cases = 0;
    for (int pairWith = firstFree + 1; pairWith < n; ++pairWith) {
        if (students[pairWith] && friends[firstFree][pairWith]) {
            students[firstFree] = students[pairWith] = false;
            cases += pairing(friends, students, n);
            students[firstFree] = students[pairWith] = true;
        }
    }

    return cases;
}

int main() {
    ios_base::sync_with_stdio(false);
    int C;
    cin >> C;
    while (C--) {
        int n, m;
        bool friends[10][10] = { false };
        bool students[10] = { true, true, true, true, true, true, true, true, true, true };
        cin >> n >> m;
        for (int i = 0; i < m; ++i) {
            int a, b;
            cin >> a >> b;
            friends[a][b] = friends[b][a] = true;
        }

        cout << pairing(friends, students, n) << endl;
    }
    return 0;
}

Back to top ↑