[ SWEA 3421 ] 수제버거 장인 (C++)

SWExpertAcademy의 수제버거장인(3421 / D5) 문제이다.

[ 문제풀이 ]

서로 어울리는 재료들만으로 버거를 만들 수 있을 때, 가능한 버거의 종류가 몇 가지인지 구해야 하는 문제이다.

들어가야 하는 재료의 갯수에는 제한이 없으며, 재료가 하나도 들어가지 않는 버거 또한 버거로 인정한다.

본인이 가장 먼저 구현한 것은 "조합" 이다. 왜 갑자기 조합일까 ?? 정확하게 말하자면 이 문제에서는 "부분집합"을 구해주어야 한다. 주어진 재료들을 하나의 큰 집합이라고 가정했을 때, 재료의 갯수에 상관없이 서로 어울리는 재료들 일부들 끼리만 묶어줘야 하기 때문에, 부분 집합을 구해주어야 한다.

그런데 조합을 구해야 하는 이유는 ?? 조합에서 "뽑아야 하는 갯수를 지정해주지 않으면" 그것이 바로 부분집합이기 때문이다.

먼저 조합을 구현할 줄 모른다면 아래의 글을 읽고 오도록 하자.

[ 조합 구현하는 법 알아보기(Click) ]

말했듯이, 조합을 구현하는 과정에서 뽑아야 하는 갯수를 지정해주지 않으면 부분집합을 구할 수 있게 된다.

따라서 조합을 구하는 재귀문에서, 종료조건을 설정해주지 않았다.

또한, 하나의 재료를 뽑을 때 마다, "기존에 뽑아놓은 재료들과 비교했을 때, 어울리지 않는 재료가 있는지" 를 확인해 주면서 재료를 선택해 주었다.

[ 소스코드 ]

#include <iostream>
#include <cstring>
#include <vector>
 
#define endl "\n"
#define MAX 25
using namespace std;
 
int N, M, Answer;
bool Flag[MAX][MAX];
bool Visit[MAX];
 
void Initialize()
{
    memset(Flag, false, sizeof(Flag));
    memset(Visit, false, sizeof(Visit));
    Answer = 0;
 
}
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b; cin >> a >> b;
        Flag[a][b] = true;
        Flag[b][a] = true;
    }
}
 
bool Check(int Num, vector<int> V)
{
    for (int i = 0; i < V.size(); i++)
    {
        int Num2 = V[i];
        if (Flag[Num][Num2] == true) return false;
    }
    return true;
}
 
void DFS(int Idx, vector<int> V)
{
    Answer++;
    
    for (int i = Idx; i <= N; i++)
    {
        if (Visit[i] == true) continue;
        if (Check(i, V) == false) continue;
 
        Visit[i] = true;
        V.push_back(i);
        DFS(i, V);
        V.pop_back();
        Visit[i] = false;
    }
}
 
void Solution()
{
    vector<int> V;
    DFS(1, V);
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}