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

문제 출처 :

https://www.acmicpc.net/problem/2422

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

우선 조합론에 관련된 문제이지만 n 범위가 200이기에 모든 경우에 대해 다 생각해보자.

아이스크림 개수는 총 3가지를 선택할 것이고 입력에 나오는 조합의 맛은 선택하면 안된다.

따라서 bfs를 통해 벡터에 오름차순으로 담기게 하여 벡터 크기가 3이 되었을 때

나오면 안되는 조합이 있는지 판별해주는 방식으로 진행하면 문제를 해결 할 수 있다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
 
using namespace std;
 
typedef pair<int, vector<int> > piv;
 
bool forbidden[202][202];
 
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < m; i++)
    {
        int from, to;
        scanf("%d %d", &from, &to);
 
        forbidden[from][to] = forbidden[to][from] = true;
    }
 
    queue<piv> q;
    for (int i = 1; i <= n; i++)
    {
        vector<int> vc;
        vc.push_back(i);
        q.push({ i,vc });
    }
    int ans = 0;
    while (!q.empty())
    {
        int here = q.front().first;
        vector<int> vc = q.front().second;
        int cnt = q.front().second.size();
        q.pop();    
        
        if (cnt == 3)
        {
            int len = vc.size();
            bool chk = false;
            for (int i = 0; i < len - 1; i++)
                for (int j = i + 1; j < len; j++)
                    if (forbidden[vc[i]][vc[j]] || forbidden[vc[j]][vc[i]])
                        chk = true;
            if(!chk)
                ans++;
            continue;
        }
        
        for (int next = here + 1; next <= n; next++)
        {
            vc.push_back(next);
            q.push({ next, vc});
            vc.pop_back();
        }
    }
 
    printf("%d\n", ans);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>