[알고스팟]소풍(PICNIC)

문제

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

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

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

입력

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

 

출력

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

 

내가푼 방법

#include <iostream>
 
using namespace std;
 
int n, m;
bool areFriends[10][10];
 
int countFriends(bool taken[10])
{
    bool finish = true;
    for (int i = 0; i < n; ++i) if (!taken[i]) finish = false;
 
    if (finish) return 1;
 
    int ret = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (!taken[i] && !taken[j] && areFriends[i][j])
            {
                taken[i] = taken[j] = true;
                ret += countFriends(taken);
                taken[i] = taken[j] = false;
            }
        }
    }
    return ret;
}
 
int main()
{
    cin.sync_with_stdio(false);
    cin.tie(false);
    cout.tie(false);
 
    int testCase;
 
    cin >> testCase;
 
    for (int i = 0; i < testCase; ++i)
    {
        cin >> n >> m;
        for (int j = 0; j < m; ++j)
        {
            int p, q;
            cin >> p >> q;
            areFriends[p][q] = areFriends[q][p] = true;
        }
 
        bool taken[10] = { false, };
        cout << countFriends(taken) << endl;
 
        for (int p = 0; p < 10; ++p)
            for (int q = 0; q < 10; ++q)
                areFriends[p][q] = false;
    }
}

종만북에서 처음에 나온 방법이다

이까지 읽고 다시 생각해서 풀어보니 종만쌤이 뭐라고 했는지 이해할 수 있었다

이렇게 짜면 예를들어 4명의 학생중 친구쌍이 (0,1), (2,3)로 주어졌을때

countFriends 내부의 2중 for문 안에서

(0,1) (2,3)의 경우를 세고 그다음 (0,1) (3,2)역시 또다른 경우의 수로 센다

그렇기 때문에 중복하여 세는 수가 많아진다는 것이다

 

다시 종만쌤의 설명에 따라 맨처음 시작하는 짝의 순서를 정해버리고 문제를 풀어보면

#include <iostream>
 
using namespace std;
 
int n, m;
bool areFriends[10][10];
 
int countFriends(bool taken[10])
{
    int firstFriend = -1;
    for (int i = 0; i < n; ++i) 
        if (!taken[i])
        {
            firstFriend = i;
            break;
        }
 
    if (firstFriend == -1) return 1;
 
    int ret = 0;
 
    for (int secondFriend = firstFriend + 1; secondFriend < n; ++secondFriend)
    {
        if (!taken[secondFriend] && areFriends[firstFriend][secondFriend])
        {
            taken[firstFriend] = taken[secondFriend] = true;
            ret += countFriends(taken);
            taken[firstFriend] = taken[secondFriend] = false;
        }
    }
 
    return ret;
}
 
int main()
{
    cin.sync_with_stdio(false);
    cin.tie(false);
    cout.tie(false);
 
    int testCase;
 
    cin >> testCase;
 
    for (int i = 0; i < testCase; ++i)
    {
        cin >> n >> m;
        for (int j = 0; j < m; ++j)
        {
            int p, q;
            cin >> p >> q;
            areFriends[p][q] = areFriends[q][p] = true;
        }
 
        bool taken[10] = { false, };
        cout << countFriends(taken) << endl;
 
        for (int p = 0; p < 10; ++p)
            for (int q = 0; q < 10; ++q)
                areFriends[p][q] = false;
    }
}

firstFriend와 secondFriend를 나눠서 짝을 지을때 순서대로 짝을 지을수 있도록 강제했다

따라서 위에 예시에서 (0,1) (2,3)을 뽑고 (0,1) (3,2)를 뽑을 수 없다

 

 

URL : https://www.algospot.com/judge/problem/read/PICNIC#