6.3 문제 : 소풍 ( 문제 ID: PICNIC , 난이도: 하)

★★★★★다시 풀어볼 문제★★★★★

알고리즘 문제 해결 전략 1권

6.3 문제 : 소풍 ( 문제 ID: PICNIC , 난이도: 하)

완전탐색 문제를 재귀로 구현.

이번에 내가 치뤘던 삼성 소프트웨어 역량 평가 1번 문제랑 흡사한 듯 보인다.

내가 그 문제를 못 풀었던 것 처럼 이 문제도 풀지 못했다. 

다시 한번 그 문제를 풀어봐야 겠다. 

생각보다 그렇게 복잡하게 생각하지 않아도 되는 문제.

단 주의할 점은 중복하는 경우의 수를 계산하는 방식.

난이도가 하라고 표기되어 있지만 나한테는 어려웠던 문제.

이 문제를 통해서 bool 타입 변수를 어떤 이름으로 선언해야 효과적인지 배울 수 있었다.

그 동안 bool 타입을 선언하고 조건문 안에서 이게 언제 true일까 false 일까 하는 고민으로 낭비되는 시간을 좀 줄일 수 있었다.

#include<iostream>
 
using namespace std;
 
int ans;
int N, M;
bool areFriends[10][10];        // 둘은 친구인가? 확인하는 bool 변수
bool havePair[10];                // 짝이 있는가? 확인하는 bool 변수
 
void counting(int n)
{
    bool finished = true;        
    int first = -1;        
    for (int i = 0; i < N; i++)
    {
        if (!havePair[i])
        {
            finished = false;
            first = i;            //중복을 제거하기 위해, 짝을 지을 때 오름 차순 순서쌍으로 구현하기 위해, 가장 작은 짝이 없는 수를 구하기.
            break;
        }
    }
 
    if (finished)
    {
        ans += 1;
        return;
    }
 
 
    
        for (int j = first+1; j < N; j++)        //가장 작은 짝이 없는 수와 그 수보다 큰 수들을 짝 짓기.
        {
            if (!havePair[first] && !havePair[j] && areFriends[first][j])
            {
                havePair[first] = true;
                havePair[j] = true;
                counting(n+1);
                havePair[first] = false;
                havePair[j] = false;
            }
        }
    
 
    return;
}
 
int main()
{
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        ans = 0;
        for (int i = 0; i < 10; i++)
        {
            havePair[i] = false;
            for (int j = 0; j < 10; j++)
            {
                areFriends[i][j] = false;
            }
        }
 
        cin >> N >> M;
 
        for (int i = 0; i < M; i++)
        {
            int a, b;
            cin >> a >> b;
            areFriends[a][b] = true;
            areFriends[b][a] = true;
        }
 
        counting(0);
 
        cout << ans << endl;
    }
 
    return 0;
}