[Algospot 알고스팟] PICNIC 소풍 C, C++언어 문제 풀이

알고리즘 문제해결전략 문제 소풍

풀이방법

재귀문을 통해 입력된 값을 탐색을 하면 됩니다. 

예제 1번

1  
4 6 
0 1 1 2 2 3 3 0 0 2 1 3 
6 10 

위의 예제의 경우 출력은 3이 나오게 됩니다. 

출력이 3이 나오기 위한 경우 : 01 23, 12 30, 13 02

2번째 입력 값을 보고 사람 수 만큼 Table의 크기를 잡고 짝이 되는 것을 찾을 때 마다 table 값을 -1로 변경 하여

table의 값이 모두 -1이 된다면 다 찾은 것이라고 생각을 했었는데, 입력 예제 3번째 TC값을 보고 재귀문을 통해서 탐색을 하는 방법을 생각하게 되었습니다.

예제 2번

1 
6 10 
0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5

01 을 먼저 찾은 경우 뒤의 짝은 23 45 가 될 수도 있고 24 35가 될 수도 있습니다. 

이렇게 되면 단순히 for문으로 탐색을 하기에는 코드가 복잡해 지기 때문에 재귀문을 이용하여 탐색을 하였으며

재귀문으로 탐색한 코드는 하단에 첨부해 두었습니다. 

[소스 코드]

#include <iostream>
using namespace std;
 
int N;
int M;
int Result;
 
int couple[50][2];
int table[10];
 
void tableReset() {
    for (int i = 0; i < 10; i++) {
        table[i] = i;
    }
}
 
int tableCheck() {
    int count = 0;
    for (int i = 0; i < N; i++) {
        if (table[i] == -1)
            count++;
    }
 
    if (count == N)
        return 1;
    else
        return 0;
}
 
void search_(int i) {
    if (tableCheck() == 1) {
        Result++;
        return;
    }
 
    if (i >= M)
        return;
 
    int num1 = couple[i][0];
    int num2 = couple[i][1];
    
    if (table[num1] != -1 && table[num2] != -1) {
        table[num1] = -1;
        table[num2] = -1;
        search_(i + 1);
        table[num1] = num1;
        table[num2] = num2;
    }
    search_(i + 1);
}
 
int main() {
    int tc;
    cin >> tc;
 
    for (int tt = 0; tt < tc; tt++) {
        cin >> N;
        cin >> M;
        tableReset();
 
        for (int i = 0; i < M; i++) {
            cin >> couple[i][0] >> couple[i][1];
        }
 
        Result = 0;
        search_(0);
        cout << Result << endl;
    }
    return 0;
}