[ALGOSPOT] PICNIC

출처 : algospot.com/judge/problem/read/PICNIC

algospot.com :: PICNIC

문제

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

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

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

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

입력

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

 

출력

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

 

 

<아이디어>

하나씩 돌면서 완전탐색, 이미 선택했다면 다음 친구로 넘어감.

 

<구현>

서로의 가능한 파트너를 vector<vector<int>> 인접리스트로 구현

check 배열은 현재 짝을 지었는지 아닌지 확인하는 배열'

pos는 0~n-1번째 친구를 의미함.

전체문제를 n개의 조각으로 나누어서

현재 파트너로 선택되지 않으면 파트너를 선택.

선택된 상태이면 다음 친구로 넘어감(재귀호출).

 

<실수한 부분>

else if(check[pos]) f(pos+1, v);

로만 했다가 1시간 정도 뻘짓

 

그곳에서 return을 하지 않으면 어떤 문제가 생기는가?

f(pos+1, v)에서 돌아오고

check[pos] = true; 를 하고 for문을 돌아버립니다.

하지만 현재 pos는 이미 앞에서 파트너로 선택된 친구.

그러므로 새로운 파트너를 선택해서는 안되고, return을 해야합니다.

 

이 코드는 처음 문제를 접하고 정답을 맞춘 코드입니다.

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
bool check[10];
int n;
int cnt;
 
void f(int pos, vector<vector<int>>& v)
{
    if(pos==n)
    {
        cnt++;
        return;
    }
    else if(check[pos])
    {
        f(pos+1, v);
        return;
    }
    check[pos] = true;
    for(int i=0;i<v[pos].size();i++)
    {
        if(!check[v[pos][i]])
        {
            check[v[pos][i]] = true;
            f(pos+1, v);
            check[v[pos][i]] = false;
        }
    }
    check[pos] = false;
}
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc;
    cin>>tc;
    while(tc--)
    {
        int m;
        cin>>n>>m;
        memset(check, false, sizeof(check));
        vector<vector<int>> v(n);
        for(int i=0;i<m;i++)
        {
            int a, b;
            cin>>a>>b;
            v[a].push_back(b);
            v[b].push_back(a);
        }
        cnt = 0;
        f(0, v);
        cout<<cnt<<endl;
    }
    return 0;
} 

 

 

 

다음 코드는 책을 보고 수정한 코드입니다. (back tracking 기법처럼 변경된 것 같습니다.)

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
bool check[10];
int n;
int cnt;
 
int f(int pos, vector<vector<int>>& v)
{
    if(pos==n) return 1;
    else if(check[pos]) return f(pos+1, v);
    int ret = 0;
    check[pos] = true;
    for(int i=0;i<v[pos].size();i++)
    {
        if(!check[v[pos][i]])
        {
            check[v[pos][i]] = true;
            ret += f(pos+1, v);
            check[v[pos][i]] = false;
        }
    }
    check[pos] = false;
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc;
    cin>>tc;
    while(tc--)
    {
        int m;
        cin>>n>>m;
        memset(check, false, sizeof(check));
        vector<vector<int>> v(n);
        for(int i=0;i<m;i++)
        {
            int a, b;
            cin>>a>>b;
            v[a].push_back(b);
            v[b].push_back(a);
        }
        cout<<f(0, v)<<endl;
        
    }
    return 0;
}

 

 

base case 에서 1씩 return하여 더해지고

현재 친구가 이미 파트너로 선정된 친구면 다음 친구로 넘어가는 것을 return 하는 것으로 한번에 해결할 수 있었습니다.

나머지 부분은 거의 같습니다.