프.알.문-무식하게 풀기<소풍>

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 중. 무식하게 풀기 1번 문제인,,,

소풍 문제입니다.

문제

안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다.

각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고

 봅니다. 예를 들어 다음 두 가지 방법은 서로 다른 방법입니다.

• (태연,제시카) (써니,티파니) (효연,유리)
• (태연,제시카) (써니,유리) (효연,티파니)

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 학생의 수 n (2 <= n <= 10) 과 친구 쌍의 수 m (0 <= m <= n*(n-1)/2) 이 주어집니다. 그 다음 줄에 m 개의 정수 쌍으로 서로 친구인 두 학생의 번호가 주어집니다. 번호는 모두 0 부터 n-1 사이의 정수이고, 같은 쌍은 입력에 두 번 주어지지 않습니다. 학생들의 수는 짝수입니다.

출력

각 테스트 케이스마다 한 줄에 모든 학생을 친구끼리만 짝지어줄 수 있는 방법의 수를 출력합니다.

예제 입력

3 
2 1 
0 1 
4 6 
0 1 1 2 2 3 3 0 0 2 1 3 
6 10 
0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5

예제 출력

1
3
4

 무식하게 풀기란, 말그대로 모든 경우의 수를 구한 후 정답에 해당되는 항들만 골라 출력하는 형식입니다. 그렇기 때문에 순환(recursive)문을 많이 이용을 합니다.  

이 문제에서도 N명의 학생들 중 M개의 친구 관계가 있고, 이 친구 관계를 고려하였을 때 친구끼리만 짝지어줄 수 있는 방법들을 무식하게 풀어내야만 하죠...... 프.알.문 책에서는

int n,m;
bool areFriends[10][10];
 
int countPairings(bool taken[10]) {
    int firstFree = -1;
    for (int i = 0; i < n; ++i) {
        if (!taken[i]) {
            firstFree = i;
            break;
        }
    }
    //기저사례 : 모두 짝이 있는 경우
    if (firstFree == -1) return 1;
    int ret = 0;
    for (int pairWith = firstFree + 1; pairWith < n; ++pairWith) {
        if (!taken[pairWith] && areFriends[firstFree][pairWith]) {
            taken[firstFree] = taken[pairWith] = true;
            ret += countPairings(taken);
            taken[firstFree] = taken[pairWith] = false;
        }
    }
    return ret;
 
}

 

MY QUESTION?

이러한 방식으로 areFirends[][] 와 firstFree, taken을 이용하여 countPairings라는 순환호출함수를 만들어주었습니다.

제가 여기서 궁금했던 점은 ret 인데요.... ret이 처음에 0을 선언되고 ret +=countPairings(taken) 부분에서 ret이 어떻게 계속 증가하는지 궁금했습니다. 말 그대로 0+0=0? 아닌가라는 의문을 갖게 되었습니다.

과연 어떻게 ret은 경우의 수가 있다면 계속 증가 할 수 있었을까요??

많은 고민 끝에 if(firstFree == -1) return 1;에서 해답을 찾을 수 있었습니다. 순환호출함수에서 가장 중요한 것은 빠져 나올 수 있는 기저사례를 만들어주는 것인데 위 문제의 기저사례는 모든 학생들이 짝을 찾았을 경우였기 때문에 firstFree==-1을 이용해 기저사례를 정해주었고, 이 때문에 한가지 경우의 수마다 1씩 증가 할 수 있었던 것이였습니다!!

이 방식을 통해 최종적으로 완성해본 코드입니다.

#include <iostream> #include <cstring> using namespace std; int n,m; bool areFriends[10][10]; int countPairings(bool taken[10]) { int firstFree = -1; for (int i = 0; i < n; ++i) { if (!taken[i]) { firstFree = i; break; } } //기저사례 : 모두 짝이 있는 경우 if (firstFree == -1) return 1; int ret = 0; for (int pairWith = firstFree + 1; pairWith < n; ++pairWith) { if (!taken[pairWith] && areFriends[firstFree][pairWith]) { taken[firstFree] = taken[pairWith] = true; ret += countPairings(taken); taken[firstFree] = taken[pairWith] = false; } } return ret; } int main() { int cnt; cin >> cnt; while (cnt--) { areFriends[10][10]; memset(areFriends, 0, sizeof(areFriends)); cin >> n >> m; for (int numFri = 0; numFri < m; numFri++) { int pair1, pair2; cin >> pair1 >> pair2; areFriends[pair1][pair2] = areFriends[pair2][pair1] = true; } bool taken[10] = { false, }; cout << countPairings(taken) << endl; } return 0; }

RESULT :

3
2 1
0 1
1
4 6
0 1 1 2 2 3 3 0 0 2 1 3
3
6 10
0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5
4

궁금하신 것이 있으시다면 댓글로 남겨주세요!~