[C++] 2422 - 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

문제 링크 : https://www.acmicpc.net/problem/2422

2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

 

먼저 V배열에 먹으면 안되는 조합 ( 1, 2 )를 1로 체크해두고 ( 탐색시 그 경우는 제외 시킨다 )

백트래킹으로 배열에 아이스크림을 하나씩 담으면서 넣는 아이스크림이 이전에 넣은 아이스크림과 같이 먹어도 되는 조합인지 검사하고 넣는다.

이 때 오름차순을 안하고 넣으면 똑같은 조합이 여러가지로 나올 수 있으므로

ex) (1, 2, 5) (1, 5, 2) (5, 1, 2) 등... 같은 조합

무조건 왼쪽에서 오른쪽으로 갈 때는 오름차순을 지키도록 해서 경우의 수를 구했다.

 

 

#include<bits/stdc++.h>
 
#define endl '\n'
 
using namespace std;
 
int N, M;
int cnt;
 
bool isuse[205];
bool V[205][205];
int arr[205];
 
int check(int l, int k)
{
    for(int i = 0; i < k; ++i)
    {
        if(V[arr[i]][l])
            return 0;
    }
 
    return 1;
}
 
void B(int k)
{
    if(k == 3)
    {
        cnt++;
        return;
    }
 
    for(int i = 1; i <= N; ++i)
    {
        if(isuse[i] == 0 && check(i, k) && arr[k-1] < i)
        {
            isuse[i] = 1;
            arr[k] = i;
            B(k+1);
            arr[k] = 0;
            isuse[i] = 0;
        }
    }
}
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
    int v1, v2;
 
    for(int i = 0; i < M; ++i)
    {
        cin >> v1 >> v2;
        V[v1][v2] = V[v2][v1] = 1;
    }
 
    B(0);
 
    cout << cnt << endl;
 
    return 0;
}