1. Brute-Force - 소풍(picnic) 문제

가능한 조합의 수를 계산하는 문제를 푸는 가장 간단한 방법은 완전 탐색을 이용해 모든 조합을 만들어 보는것이다.

재귀 호출을 이용해 문제를 해결하기 위해 전체 과정을 조각으로 나누어보자.

각 조각은 n명의 학생들 중 두명의 학생을 짝지어 주는 것으로 나눌 수 있다.

그러면 문제의 형태는 아직 짝을 찾지 못한 학생들의 명단이 주어질 때 친구끼리 둘씩 짝을 짓는 경우의 수를 계산하는 형태가 된다.

즉 재귀함수에서 다음을 필요로 한다.

1. n명의 학생들이 각각 짝이 지어졌는지 확인할 수 있는 배열(학생들의 명단)

2. 친구들의 정보를 가지고 있는 배열

각 재귀호출에서 두명의 학생을 짝 지어주고 학생들의 명단을 수정한 뒤 나머지 학생들에 대해 같은 재귀함수를 호출하여 준다.

그리고 모든 학생들이 짝지어졌다면 방법의 수를 1 증가시킨다.

문제 풀이

#include <iostream>

#include <vector>

#include <string.h>

using namespace std;

int res = 0;

void makePartner(int *students, int n, int **friends) {

int smallest = n;  // 현재 짝을 지어주고자 하는 학생

for (int i = 0; i < n; i++) {

if (students[i] == 0) {

smallest = i;

break;

}

}

// students 배열 값이 모두 1이면(모두 짝지어졌으면) 방법수 +1

if (smallest == n) {

res++;

return;

}

for (int i = smallest + 1; i < n; i++) {

// 짝을 지어주고자 하는 학생과 i번째학생이 서로 친구이며 i번째학생이 아직 짝지어지지 않았을때

if (friends[smallest][i] == 1 && students[i] == 0) {

// 두 친구를 짝지어주고 남은 학생들에 대해서 반복한다.

students[smallest] = 1;  

students[i] = 1;

makePartner(students, n, friends);

students[smallest] = 0;

students[i] = 0;

}

}

}

int main() {

int c;  // 테스트 케이스 수

int n; // 학생 수

int m; // 친구 쌍의 수

vector<int> result; // 결과값 배열

cin >> c;

for (int i = 0; i < c; i++) {

cin >> n;

cin >> m;

int **friends =  new int*[n];  // 입력 친구쌍 배열

int *students = new int[n];  // 각 학생들 짝 지어졌는지 확인하기 위한 배열(0: 짝지어지기 전, 1:후)

memset(students, 0, sizeof(int)*n);

for (int a = 0; a < n; a++) {  // friends 배열 동적할당(n*n)

friends[a] = new int[n];

memset(friends[a], 0, sizeof(int)*n);

}

for (int j = 0; j < m; j++) {

int first;

int second;

cin >> first;

cin >> second;

friends[first][second] = 1;  // (first,second) 가 친구이면 1

friends[second][first] = 1;

}

makePartner(students, n, friends);

result.push_back(res);

res = 0;  // 0으로 다시 초기화

for (int i = 0; i < n; i++) {

delete[] friends[i];

}

delete[] friends;

delete[] students;

}

for (int i = 0; i < result.size(); i++) {

cout << result[i] << endl;

}

}

makePartner(...) 함수는 남아있는 학생들 중 번호가 가장 작은 학생(smallest)에 대해서 해당 학생의 바로 뒤부터 탐색하여 친구를 찾아 짝을 지어준다.

이 때 친구를 찾아 짝을 지어준 뒤 학생 명단을 수정하고 (짝지은 두 학생을 짝지어줬다고 표시) 남아있는 학생에 대해서 재귀호출을 하게 된다.

이 재귀 호출이 끝나면 현재 짝을 지어주는 학생(smallest)의 다른 친구를 찾기 위해서 

이전에 짝지어준 두 학생에 대해서 명단을 다시 수정해줘야 한다. (smallest와 i번째 학생이 짝지어지지 않았다고 표시)

조합의 경우의 수를 셀 때 주의해야 할 점은 중복으로 세는 문제이다.

예를 들어 (0,1)(2,3) 으로 짝지은 것과 (2,3)(0,1) 또는 (1,0)(2,3) 으로 짝지은 것은 모두 같은 경우이지만

반복문을 항상 0부터 끝까지 돌리면서 경우의 수를 세게 되면 이 경우들을 중복으로 세게 될 수가 있다.

이와 같은 문제를 해결하기 위해 특정 형태를 갖는 답만 세도록 강제할 수 있다.

흔히 사용하는 방법은 같은 답들 중에서 사전순으로 가장 먼저 오는 답 하나만 세는 것이다.

이 방법을 사용하기 위해 각 단계에서 남아있는 학생들 중 번호가 가장 작은 학생(smallest)의 짝을 찾아주도록 한다.

답의 수의 상한

재귀 호출 알고리즘은 답의 수에 정비례하는 시간이 걸린다.

따라서 실제로 프로그램을 짜기 전에 답의 수가 얼마나 될지 예측해보고 시간이 얼마나 오래 걸릴지를 확인해야 한다.

이 문제의 경우 가장 많은 답을 가질 수 있는 경우는 10명의 학생이 모두 서로 친구인 경우이다.

이 때 답의 수는 9*7*5*3*1 = 945가 된다.

(첫번째 학생은 9명 중 선택 가능 * 두번째 학생은 남아있는 7명 중 선택 가능 * ... )