[Algorithm Strategies] 02. Exhaustive Search - Picnic

1. Exhaustive Search

1.1 Picnic - Recursive Function

1.1.1 Problem

- 소풍 때 학생들을 두 명씩 짝을 지어 행동

   - 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문

     - 항상 서로 친구인 학생들끼리만 짝을 지어야 함

 - 각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 방법의 수를 계산하는 프로그램 작성

1.1.1.1 Input

 - 입력의 첫 줄에는 테스트 케이스 수, 각 테스트 케이스의 첫 줄에서는 학생의 수, 친구 쌍의 수가 주어짐

   - 다음 줄에 m개의 정수 쌍으로 서로 친구인 두 학생의 번호가 주어짐

     - 번호는 모두 0부터 n - 1사이의 정수이고, 같은 쌍은 입력에 두번 주어지지 않음, 학생들의 수는 짝수

1.1.2 Algorithm Strategy

 - 종료 조건을 걸어 친구들이 모든 짝을 이루었을 경우 정답 하나를 찾았으므로 1을 반환하여 더해줌

 - 친구가 짝을 이미 찾았을 때, 못찾았을 때를 나누어 친구 두명을 골라서 친구인 지 아닌지 확인

   - 이때 친구인 경우 친구가 짝을 찾았으므로 더이상 발견되지 않게 설정

     - 재귀 함수를 호출하여 다른 짝을 찾아 보고 이전 함수에서 다른 짝에 대한 정보도 있으므로 친구의 짝을 없앰

 - 이때 중복이 일어나는 경우를 방지하여 항상 특정 형태의 갖는 답을 세는 것

   - 같은 답 중에서 사전순으로 가장 먼저 오는 답 하나만을 세는 것

     - 각 단계에서 남아 있는 학생들 중 가장 번호가 빠른 학생의 짝을 찾아 주면 됨 

1.1.3 implementation

vector<vector<bool>> friends; bool temp[10]{ false }; exhaustive.countPairing(4, temp);
int Exhaustive::countPairing(int number, bool taken[10]);

- 종료조건, 즉 가장 먼저 오는 친구가 없는 경우 짝을 모든 찾은 경우 이기 때문에 1을 반환

int firstFriend = -1;
for (int i = 0; i < number; i++) if (!taken[i]) { firstFriend = i; break; }
if (firstFriend == -1) return 1;

   - 처음 만난 친구와 다음에 만날 친구를 찾아 서로 친구인 경우

     - 서로 짝이 되었으므로 재귀 함수로 인해 다음 친구들이 걸리지 않도록 설정

       - 이 후 다른 버전의 짝을 찾기 위해 짝을 찾은 친구들을 풀어 다른 친구들의 짝을 찾는 방법을 선택

for (int i = firstFriend + 1; i < number; i++)
    if (!taken[i] && friends[firstFriend][i])
    {
        taken[i] = taken[firstFriend] = true;
        ret += countPairing(number, taken);
        taken[i] = taken[firstFriend] = false;
    }
return ret;