안녕하세요
PICNIC 문제를 풀고 있는데요
시간 초과가 발생하고 있습니다.
혹시 제가 풀려는 방법으로는 시간초과를 개선할 수 없는지가 궁금해서요 확인이 가능하시면 부탁드립니다^{^}

PICNIC 문제는 모든 사람에게 짝을 지워 주는 문제 입니다.

그래서 저희 해결법은

1. 비트연산을 통해 모든 경우의 수를 FOR문을 돌린다.
2. 비트의 값이 1인 경우 짝을 지여 준다.
3. 만약 모든 사람이 짝이 지어져 있으면 답을 ++ 한다.
4. 아니면 빠져나와서 그다음 케이스로 넘어간다

우선 짝이 될수 있는 CASE들을 구조체에 담아서
위의 CASE를 수행하였는데요

해당 방법으로는 시간초과를 벗어날 방법이 없을까요??

코드

#include<iostream>

using namespace std;


#define MAX 100

int howmanypeople; // 총 학생 수
int howmanygroup;// 총 그룹 수

bool check_answer = true;
bool skip_test = false;

int answer_cnt=0;

typedef struct node{

    int first_num;
    int second_num;

}Group;


Group group[MAX];


bool already_visit[MAX] = {false,};

void input_(){

    cin >> howmanypeople;
    cin >> howmanygroup;

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

        cin >> group[i].first_num;
        cin >> group[i].second_num;
    }

}

void print_(){

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

        cout <<" "<< group[i].first_num<< " ";
        cout << group[i].second_num;

    }
    cout << endl;
}

void init_visit(){

    check_answer = true;
    skip_test = false;
    for (int i = 0; i < howmanypeople; i++){

        already_visit[i] = false;

    }
}

void init_(){
    skip_test = false;
    answer_cnt = 0;


/*
    for (int i = 0; i < howmanygroup; i++){

        group[i].first_num = 0;
        group[i].second_num = 0;
    }
*/
howmanygroup=0; 
howmanypeople=0;
    
}

void solving(){

    int first_num;
    int second_num;


    // 모든 TC를 계산

    //cout << (1 << howmanygroup )<< endl;

    for (int i = 0; i <(1 << howmanygroup); i++){ // 비트 검색을 통해 모든 경우의 수 검색
        for (int j = 0; j <howmanygroup;j++){

            if (i & (1<<j)){ // 값이 1인 경우만 짝 찾기를 수행

                first_num = group[j].first_num; // 첫번째 짝
                second_num = group[j].second_num; // 두번쨰 짝


                if (already_visit[first_num] == true || already_visit[second_num] == true){ // 이미 짝이 있으면
                    skip_test = true; // 정답 count하는 것을 skip
                    break; // 테스트를 하지 않고 빠져 나온다
                }
                

                if (already_visit[first_num] == false && already_visit[second_num] == false){ // 짝이 없으면 짝을 만들어 준다

                    already_visit[first_num] = true;
                    already_visit[second_num] = true;

                }

            }


        }
        if (!skip_test){  

            // 여기서 모두 짝이 있는지를 판단
            for (int z = 0; z < howmanypeople; z++){

                if (already_visit[z] == false){ // 짝이 없으면 스킵한다.

                    check_answer = false;
                    break;
                }
            }

            if (check_answer){// 모두 true면 모두 짝이 있으므로 정답 ++

                answer_cnt++;
            }
        
        }


        init_visit();
    }


}

int main(int argc, char** argv)
{
    int test_case;
    int T;
    cin >> T;

    for (test_case = 1; test_case <= T; ++test_case)
    {

        input_();
    //  print_();
        solving();


        cout << answer_cnt << endl;
        init_();



    }
    return 0;
}