무식하게 풀기(완전 탐색) - 소풍

 

무식하게 풀기(완전 탐색) - 소풍

 

 

문제 출저 - 알고스팟 https://algospot.com/judge/problem/read/PICNIC

 

 

 

 

 

풀이생각

1. 입력되는 n, m값이 작다.

 => 브루트포스(완전탐색)으로 풀자

2. index로 처리할 수 있는 bool 필요 (쌍 맺기 위해서)

3. 짝을 이미 맺었는지 학생마다 확인필요

 => bool 배열 생성. 재귀로 돌려주기

 => 매개변수로.

4. 중복을 제거해야 한다.

 => 오름차순으로 맺어주자.

 => 앞 번호 친구부터 검사해서 짝을 맺어주자.

 

 

 

answer code (알고리즘 문제해결전략 p158~159)

#include <iostream>
#include <cstring>
 
using namespace std;
 
bool check[10][10];
int n, m;
 
int func(bool hasF[10]) {
    int first = -1;
    
    for (int i = 0; i < n; ++i) {
        if (!hasF[i]) {
            first = i;
            break;
        }
    }
    
    if (first == -1) return 1;
    
    int ret = 0;
    for (int j = first+1; j < n; ++j) {
        if (!hasF[j] && check[first][j]) {
            hasF[first] = true;
            hasF[j] = true;
            ret += func(hasF);
            hasF[first] = false;
            hasF[j] = false;
        }
    }
    return ret;
}
 
int main(void) {
    cin.sync_with_stdio(false);
 
    int t;
    bool hasF[10];
    cin >> t;
 
    while (t--) {
        cin >> n >> m;
        memset(check, false, sizeof(check));
        memset(hasF, false, sizeof(hasF));
        for(int i=0; i<m; ++i){
            int a, b;
            cin >> a >> b;
            check[a][b] = true;
            check[b][a] = true;
        }
        cout << func(hasF) << "\n";
    }
    return 0;
}

 

 

 

 

feedback

● 가능한 조합의 수를 계산하는 문제는 브루트포스 생각해보기

● index로 처리할 수 있는 쌍이 나오면 이차원배열 생각하기. bool check[10][10]

● (재귀) 다음번 for문을 위해서 false로. -> 다음 순번 진행위해 초기화해주는 것.

● 경우의 수를 셀 때 중복문제가 자주 일어남에 신경쓰자.