[종만북] 소풍

문제

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

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

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

입력

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

풀이

결국 알고리즘은 책을 참고하긴 했다. 이게 난이도 하 문제라고 하는데 전혀 난이도 하 같지도않고, c++가 아직 익숙하지도 않아서 더욱 어렵게 느껴졌다.

먼저, 두 학생의 번호로 친구를 나타내는 2차원 배열을 만들어줬다. 그리고 입력 받은 변수들을 조작해서 입력값을 알맞게 딱딱 넣어주고, 이제 경우의 수를 세는 함수를 만들어주면 된다.

알고리즘은 다음과 같다.

1. 남은 학생들 중 번호가 가장 빠른 학생을 찾는다.

2. 그 학생과 짝을 이루는 학생의 번호를 찾고, 두 학생을 제외시킨 나머지 학생들을 재귀 함수로 넘긴다.

3. 1,2번 과정 반복

4. 여기까지 보면 기저사례가 판단이 된다. 기저사례는 모든 학생이 짝을 찾았을 경우다.

코드

#include <iostream>

using namespace std;

int C, n, m; // n : 학생의 수, m : 친구 쌍의 수

int picnic(bool taken[10], int friends[10][10]){
    int minnum = -1;
    for (int i = 0; i<n; i++)
        if(!taken[i])
        {
            minnum = i;
            break;
        }

    // 기저사례
    if (minnum == -1)
        return 1;

    int ret = 0;
    // 여기 판단하는 게 가장 어려웠다.
    for (int i = minnum+1; i<n; i++){
        if(!taken[i] && friends[minnum][i] == 1){
            taken[i] = true;
            taken[minnum] = true;
            ret += picnic(taken,friends);
            taken[i] = false;
            taken[minnum] = false;
        }
    }

    return ret;
}
int main(){
    cin >> C;
    int answer[C];
    for(int T = 0; T < C; T++){ // 테스트 케이스 수 만큼 반복.
        int friends[10][10] = {0};
        cin >> n >> m;
        bool taken[10] = {false};
        int numbers[2*m];
        for(int i = 0; i<2*m; i++) {
            cin >> numbers[i];
        }

        for(int i = 0; i<m; i++){
            int a = numbers[2*i];
            int b = numbers[2*i+1];
            friends[a][b] = 1;
            friends[b][a] = 1;
        }

        answer[T] = picnic(taken,friends);
    }
    for (int i = 0; i < C; i++)
        cout << answer[i] << endl;
}

문제를 풀어보고 싶다면

링크 : 알고스팟- 소풍

근데 사이트가 오래돼서 좀 이상하다. 컴파일러가 최신 게 아닌 듯. 이상한 오류를 하나씩 잡는다.