algospot PICNIC

문제 링크입니다: https://algospot.com/judge/problem/read/PICNIC

책에 나와있는대로 재귀를 이용하여 문제를 해결했습니다.

/*

각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때,

학생들을 짝지을 수 있는 방법의 수를 계산하는 프로그램을 작성한다.

*/

#include <iostream>

#include <cstring>

using namespace std;

 

int total; //학생 수

bool areFriends[10][10]; //서로 친구인가 확인을 위한 이차원 배열

 

//taken[i]=i번째 학생이 짝을 찾았는지 여부

int countPairings(bool taken[10])

{

        //남은 학생들 중 가장 번호가 빠른 학생 찾는다

        int firstStudent = -1;

 

        for (int i = 0; i < total; i++)

        {

               if (!taken[i])

               {

                       firstStudent = i;

                       break;

               }

        }

        //기저 사례: 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료

        if (firstStudent == -1)

               return 1;

        int result = 0;

        //이 학생과 짝지을 학생 결정

        for (int i = firstStudent + 1; i < total; i++)

        {

               if (!taken[i] && areFriends[firstStudent][i])

               {

                       taken[firstStudent] = taken[i] = true; //짝이 정해져있는 상태에서

                       result += countPairings(taken); //재귀

                       taken[firstStudent] = taken[i] = false; //다른 경우의 수 찾기 위해 짝 해제

               }

        }

        return result;

}

 

int main(void)

{

        int test;

        bool taken[10];

 

        cin >> test;

        if (test < 0 || test>50)

               exit(-1);

        for (int i = 0; i < test; i++)

        {

               int pair;

               cin >> total >> pair;

               if (total < 2 || total>10 || pair < 0 || pair > (((total)*(total - 1)) / 2))

                       exit(-1);

               //초기화

               memset(areFriends, false, sizeof(areFriends));

               memset(taken, false, sizeof(taken));

 

               for (int j = 0; j < pair; j++)

               {

                       int student1, student2;

                       cin >> student1 >> student2;

                       areFriends[student1][student2] = areFriends[student2][student1] = true;

               }

               cout << countPairings(taken) << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

참고: [프로그래밍 대회에서 배우는 알고리즘 문제해결전략]