알고리즘 문제해결전략 문제6.3 소풍(ID: PICNIC)

문제

안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다.

각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 봅니다. 예를 들어 다음 두 가지 방법은 서로 다른 방법입니다.

• (태연,제시카) (써니,티파니) (효연,유리)
• (태연,제시카) (써니,유리) (효연,티파니)

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 학생의 수 n (2 <= n <= 10) 과 친구 쌍의 수 m (0 <= m <= n*(n-1)/2) 이 주어집니다. 그 다음 줄에 m 개의 정수 쌍으로 서로 친구인 두 학생의 번호가 주어집니다. 번호는 모두 0 부터 n-1 사이의 정수이고, 같은 쌍은 입력에 두 번 주어지지 않습니다. 학생들의 수는 짝수입니다.

출력

각 테스트 케이스마다 한 줄에 모든 학생을 친구끼리만 짝지어줄 수 있는 방법의 수를 출력합니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53	#include <iostream> #include <cstring> using namespace std;   bool areFriend[10][10];    // 친한친구 배열 int student;    // 학생 수 int Solution(bool taken[10]) {     int firstFree = -1;     for (int i = 0; i < student; i++)         if (taken[i] == false)    // i = 0~(student-1) 까지 전체 학생을 검사하여 짝을 짓지못한 학생을 찾아낸다.         {             firstFree = i;             break;         }     if (firstFree == -1) return 1;    // 학생들이 모두 짝을 이루었으므로 1 증가     int ret = 0;    // ret : 짝을 지을수 있는 경우의 수     for(int i=firstFree+1; i<student; i++)         if (!taken[firstFree] && !taken[i] && areFriend[firstFree][i])         {             taken[firstFree] = taken[i] = true;    // 아직 짝을 짓지못한 친한 학생 taken[firstFree]와 taken[i]를                                                 // 짝을 지은 학생(true)로 갱신하여 Solution 함수를 재귀호출한다.               ret += Solution(taken);    // 짝을 지은 학생들을 true처리하고 함수를 재호출한다.                taken[firstFree] = taken[i] = false; // 아직 짝을 짓지못한 학생들중 taken[firstFree] 학생과                                                   // 친한 학생을 더 찾기위해 false로 초기화해준다.         }     return ret; }   int main(void) {     int testcase;     bool taken[10];     cin >> testcase;     while (testcase--)     {         int cpNum;         cin >> student >> cpNum;         memset(areFriend, false, sizeof(areFriend));    // 친한 친구 배열 false로 초기화         memset(taken, false, sizeof(taken));    // 학생들의 상태를 false로 초기화         while (cpNum--)         {             int a, b;             cin >> a >> b;             areFriend[a][b] = true;             areFriend[b][a] = true;         }         cout << Solution(taken) << endl;;     }     return 0; } Colored by Color Scripter	cs

 

알고리즘 200일 프로젝트 - 3day

알고리즘 문제해결 전략 6.3 소풍(ID:PICNIC)

난이도 하 문제였음에도 불구하고 이해하는데 매우 힘들었다. ㅠㅠ

내일도 열심히!