[알고스팟] 소풍 - 완전 탐색, 재귀

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장.

 

소풍(링크)

재귀적으로 생각하기

학생의 명단이 주어지면 둘 씩 짝 짓는 경우의 수를 계산한다. 두 학생을 짝 짓는 작업을 하나의 작업 조각으로 보면 재귀 함수는 아직 짝을 찾지 못한 학생의 명단이 주어질 때 두 학생을 짝 지어주는 작업을 반복한다.

중복으로 세는 문제

1번 3번을 짝 짓는 것과 3번 1번을 짝 짓는 것은 별개의 경우로 세면 안 된다. 이처럼 중복으로 세는 문제를 다루는 한가지 방법은 항상 특정 형태의 답만을 세는 것이다. (조합을 구할 때 동일한 원소들이 순서가 다르게 선택되어 별개의 경우가 되지 않도록 고르는 순서를 강제하는 것과 같다.)

무식하게 풀 수 있을까?

이 문제가 가장 많은 답을 가지는 입력은 열 명의 학생이 모두 서로 친구인 경우. 가장 빠른 번호의 학생이 선택 가능한 짝은 아홉, 그 다음 학생은 일곱을 선택할 수 있다. 따라서 9 x 7 x 5 x 3 x 1 = 945 의 상한을 가진다.

 

#include <iostream>
#include <vector>
using namespace std;

#define MAX_STUDENT_NUM 10
int numOfStudents;
bool weAreFriends[MAX_STUDENT_NUM][MAX_STUDENT_NUM];

int picnic(bool isPaired[MAX_STUDENT_NUM]) {
    int front = -1;
    for (int i = 0; i < numOfStudents; ++i) {
        if (isPaired[i] == false) {
            front = i;
            break;
        }
    }
    if (front == -1) return 1;

    int ret = 0;
    for (int i = front + 1; i < numOfStudents; ++i) {
        if (isPaired[i] == false && weAreFriends[front][i]) {
            isPaired[front] = isPaired[i] = true;
            ret += picnic(isPaired);
            isPaired[front] = isPaired[i] = false;
        }
    }

    return ret;
}

int main() {
    int C; cin >> C;
    int numOfPairs;
    bool isPaired[MAX_STUDENT_NUM];
    vector<int> answers;

    while(C-- > 0) {
        cin >> numOfStudents >> numOfPairs;

        for (auto& e: isPaired) e = false;
        for (int i = 0; i < MAX_STUDENT_NUM; ++i) 
            for (auto& e: weAreFriends[i]) e = false;

        for (int i = 0; i < numOfPairs; ++i) {
            int f1, f2; cin >> f1 >> f2;
            weAreFriends[f1][f2] = weAreFriends[f2][f1] = true;
        }
        answers.push_back(picnic(isPaired));
    }

    for (auto e: answers) cout << e << " ";
    cout << endl;

    return 0;
}