[C++] Algospot - 소풍(PICNIC)

www.algospot.com/judge/problem/read/PICNIC

algospot.com :: PICNIC

<풀이>

1. 학생 수와 친구 정보를 입력받는다.

2. 모든 학생의 짝을 지으면서, 서로 친구인지 확인한다.

3. 짝이 모두 지어진 경우의 개수를 출력한다.

 

<해법>

1. 모든 학생의 짝을 지을 때, 중복을 처리하는 방법

=> 모든 학생의 짝을 지을 때, 다음과 같은 중복들이 있습니다. 학생 수는 6명이라고 가정하겠습니다.

 

첫 번째는, (0 1), (2 3), (4 5)로 짝을 짓고, (1 0), (3 2), (5 4)로 또 짝을 짓는 경우입니다. 친구끼리 순서는 상관이 없기 때문에 중복됩니다. 

두 번째는, (0 1), (2 3), (4 5)로 짝을 짓고, (2 3), (4 5), (0 1)로 또 짝을 짓는 경우입니다. 짝끼리 순서는 상관이 없기 때문에 중복됩니다.

 

저는 이 문제를 풀기 전에, '수학적으로 어떻게 풀었지?'를 먼저 생각하였습니다.

'짝 개수를 찾는 경우의 수를 어떻게 구했더라?'

 

(6C2 x 4C2 x 2C2) / 3! 이었습니다.

 

위 수식에서 중복의 힌트를 얻었습니다. 

6C2에서 C는 첫 번째 중복의 경우를 제거합니다. 친구끼리 순서는 상관이 없으므로, C(조합)을 사용합니다.

3!은 두 번째 중복의 경우를 제거합니다. 짝 끼리 순서는 상관이 없으므로, 3개의 짝을 세우는 순서(3!)로 나눕니다.

 

그렇다면 코드로 두 개의 중복을 어떻게 제거해야 할까요?

 

첫 번째 중복의 제거는 '앞의 친구가 무조건 숫자가 더 작다'의 로직을 사용합니다. (0 1)은 가능하지만 (1 0)은 불가능하게 만드는 것입니다.

두 번째 중복의 제거는 '앞 짝의 첫 번째 친구의 숫자가 더 작다'의 로직을 사용합니다. (0 1), (2 3)은 가능하지만 (2 3), (0 1)은 불가능하게 만드는 것입니다.

 

#include <iostream>
#include <string.h>
 
using namespace std;
 
int n, m;
bool areFriendsMap[10][10];
bool visited[10];
int answer;
 
//모든 친구쌍 만들어 보기
void makeFriends(int pairCnt) {
 
    //종료조건 : 친구쌍을 모두 만들었을 경우
    if (pairCnt == n / 2) {
        answer++;
        return;
    }
 
    //짝을 찾아야할 다음 친구 찾기(번호가 가장 작은 친구) -> 분모의 3! 부분
    int firstPerson = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            firstPerson = i;
            break;
        }
    }
 
    //친구의 짝 찾기 -> 6C2, 4C2, 2C2의 C(조합) 부분
    for (int i = firstPerson + 1; i < n; i++) {
 
        //짝이 없고, 둘이 친구인 경우 -> 짝 만들기
        if (!visited[i] && areFriendsMap[firstPerson][i]) {
 
            visited[firstPerson] = true, visited[i] = true;
 
            makeFriends(pairCnt + 1);
 
            visited[firstPerson] = false, visited[i] = false;        
        }
    }
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
        
        //초기화
        n = 0; m = 0;
        memset(areFriendsMap, false, sizeof(areFriendsMap));
        memset(visited, false, sizeof(visited));
        answer = 0;
 
        //입력
        cin >> n >> m;
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            areFriendsMap[a][b] = true; areFriendsMap[b][a] = true;
        }
 
        //해법
        /*
        가능한 친구쌍 모두 만들어보기
        */
        makeFriends(0);
 
        //출력
        cout << answer << "\n";
    }
 
    //종료
    return 0;
}

 

브루트포스에 대해 알아볼 수 있는 문제였습니다.