c++) 6장 - '소풍' 문제풀이

재귀호출을 사용한 간단한 예제문제를 풀어보겠습니다

example)

각 학생들의 쌍에 대해 서로 친구일 때만 짝을 지을 수 있는 방법의 개수를 구해보자

첫 줄에 테스트 케이스 C(C<=50)

각 테스트 케이스의 첫 줄에는 학생의 수 n(2<=n<=10), 친구 쌍의 수 m(0<=m<=n(n-1)/2)이 주어진다

그 다음줄에는 m개의 친구 쌍에 대한 정보가 주어진다  

 

• 재귀호출 사용시 주의점

재귀호출을 사용할 경우 같은 답을 중복으로 세는 경우가 흔하게 발생하게 됩니다.

이를 해결하기 위한 가장 좋은 방법은 "사전순"으로, 즉 "가장 먼저 오는 답" 하나만을 세는 것입니다.

예를들어 (2,3) (0,1) 또는 (1,0) (2,3) 은 count 하지 않지만

(0,1) (2,3) 은 count 할 수 있는것입니다.

 

이 속성을 사용하기 위해서, "선택되지 않은 학생들 중에 가장 번호가 빠른 학생의 짝만 찾아주도록" 하면 됩니다.

이렇게 한다면 앞의 2가지 잘못된 경우를 해결할 수 있을지 살펴봅시다.

1. (2,3) (0,1) 의 경우 가장 빠른 학생부터 짝을 지어주기 때문에 성립할 수 없습니다.

2. (1,0) (2,3) 의 경우 가장 빠른 학생의 짝은 번호가 더 클 수 밖에 없기때문에 (1,0)은 성립할 수 없습니다.

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <vector>
using namespace std;

int friends[10][10];

int checkPair(bool isChecked[10], int N) {
    // 남은 사람들 중 가장 번호가 빠른 학생을 찾는다
    int firstFriend = -1;
    for(int i=0; i<N; i++) {
        if(!isChecked[i]) {
            firstFriend = i;
            break;
        }
    }
    // 기저 사례 : 만약 짝을 지을 남은 사람이 없으면 방법을 찾은것이므로 종료한다
    if(firstFriend == -1) return 1;
    int ret = 0;
    // 짝을 지을 사람을 결정한다
    for(int next = firstFriend + 1; next < N; next++) {
        if(!isChecked[next] && friends[firstFriend][next]) {
            isChecked[next] = isChecked[firstFriend] = 1;
            ret += checkPair(isChecked,N);
            isChecked[next] = isChecked[firstFriend] = 0;
        }
    }
    return ret;
}

int main()
{
    int c,n,m;
    scanf("%d",&c);
    for(int j=0; j<c; j++) {
        scanf("%d %d",&n,&m);
        for(int i=0; i<m; i++) {
            int a,b;
            scanf("%d %d",&a,&b);
            // 한쪽이 친구면 다른쪽도 친구다
            friends[a][b] = 1;
            friends[b][a] = 1;
        }
        bool isChecked[10];
        int result = checkPair(isChecked,n);
        printf("%d\n",result);
        for(int l=0; l<10; l++)
            for(int k=0; k<10; k++)
                friends[l][k] = 0;
    }
}

 

 

입력

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