[Brute-force] PICNIC 피크닉

#include <iostream>
#include <vector>
#include <utility>
 
int picnic(std::vector<std::pair<int, int>>& friendPairList, bool* isInclude, int studentNum, int index, int includeCount)
{
    int ret = 0, first = 0, second = 0;
 
    if(includeCount == studentNum) return 1;
    if(index == friendPairList.size())  return 0;
    
    first = friendPairList[index].first;
    second = friendPairList[index].second;
 
    ret += picnic(friendPairList, isInclude, studentNum, index+1, includeCount);
    
    if(!(isInclude[first] || isInclude[second])) 
    {
        isInclude[first] = true; isInclude[second] = true;
        ret += picnic(friendPairList, isInclude, studentNum, index+1, includeCount + 2);
        isInclude[first] = false; isInclude[second] = false;
    }
    return ret;
}
 
int main(void)
{
    int testCase = 0, studentNum = 0, friendPairNum = 0;
    int first = 0, second = 0; 
    
    std::cin>>testCase;
    for(int i = 0; i < testCase; i++)
    {
        std::cin>>studentNum;
        std::cin>>friendPairNum;
        std::vector<std::pair<int,int>> friendList;
        bool* isInclude = new bool[studentNum] {false, };
        for(int j = 0; j < friendPairNum; j++)
        {
 
            std::cin>>first;
            std::cin>>second;
            friendList.push_back(std::make_pair(first, second));
        }
        
        std::cout<<picnic(friendList, isInclude, studentNum, 0, 0)<<'\n';
        delete[] isInclude;
    }
}

 

1. 완전탐색

2. 재귀

3. 데이터 자료 구조?

    pair? map? array? vector? set?

4. 더 빨리 풀 수 있는지?

   남은 학생들 중 가장 번호가 빠른 학생부터 찾아나가면 더 빠른 시간안에 문제를 해결 할 수 있을 것 이다.

   위의 풀이는 아무짝도 선택안하는 등 쓸모없는 계산이 포함되어있다. 

 

 

 

PICNIC