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

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

[ 문제풀이 ]

어울리지 않는 재료들을 함께 넣을 수 없을 때, 화섭이가 만들 수 있는 버거의 종류를 구해야 하는 문제이다.

가장 먼저 본인이 생각한 것은 "조합 구현하기" 이다.

조합을 구현한 이유는 버거에 넣은 재료를 선택해주기 위해서인데, 재료를 넣는 순서에 따라서 버거가 달라지지 않기 때문이다. 예를 들어서 1번 2번 재료 2개를 넣어서 버거를 하나 만들었는데, 이 후에, 2번 1번 재료 2개를 넣어서 새로운 버거를 만들 수 있는 것은 아니기 때문이다. 즉 ! 재료들은 순서에 영향을 미치지 않기 때문에, 순열이 아닌 조합을 구현해 주었다.

일반적인 조합이라면, 뽑아야 하는 원소의 갯수를 지정해주어야 하지만, 이 문제 같은 경우에는 재료가 하나도 들어가지 않더라도 그 자체만으로도 하나의 버거가 될 수 있고, 재료가 1개만들어가더라도, 2개가 들어가더라도, 몇 개가 들어가더라도 상관없이 버거가 될 수 있다. 즉 ! 뽑아야 하는 원소의 갯수를 지정할 수가 없다.

따라서, "조합을 구현하되, 뽑아야 하는 원소의 갯수 제한 없이 구현함으로써 '부분 집합' 을 구현" 한 것이다.

아직 조합에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 조합 알아보기(Click) ]

조합을 구현할 때, 2가지 조건을 통해서 구현해 주었다.

첫 번째 조건은 뽑았던 재료를 중복해서 뽑지 않는 것

두 번째 조건은 현재 뽑으려는 재료와 기존에 뽑아놓았던 재료들과 비교해서 어울리지 않는 재료가 있는지 판단 해 주었다.

만약 판단해서 어울리지 않는 재료가 있다면 그 재료는 뽑아주지 않았다.

따라서, 재료를 하나 뽑을 때 마다 뽑은 재료를 저장하기 위해서, 조합을 구현할 때 매개변수로 Vector를 하나 선언해서 뽑은 재료들에 대한 관리를 해 주었다.

[ 소스코드 ]

#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;
}