[SWEA] 3421 수제 버거 장인

출처: SWEA

Approach

버거를 만들 때, 재료가 하나도 없는 것도 하나의 버거가 될 수 있다.

즉, N개의 자료 중에 하나도 선택하지 않는 경우도 포함해야 한다.

 

조합(combination) 을 구현한다.

- 재료 자체를 중복해서 선택할 수 없다.

▶ 순열과 조합  

순열과 조합 (백준 N과 M 시리즈)

▶ N과 M (2)   (중복 허용하지 않는 조합)

[BOJ] 백준 15650 N과 M (2)

 

- 선택한 재료가 문제 조건에 제시한 어울리지 않는 재료인지 확인

ex) impossible[2][3] = true 인 경우, {2, 3} 재료 조합이 불가한 것을 의미

      순서가 상관없으므로 자동적으로 impossible[3][2] = true 이다.

---

#include <stdio.h>

const int MAX_N = 20 + 2;
int N, M, ans, TC, ia, ib;
bool impossible[MAX_N][MAX_N];
bool visited[MAX_N];
int selected[MAX_N];

void init()
{
    for (int i = 0; i < MAX_N; ++i)
    {
        visited[i] = false;
        for (int j = 0; j < MAX_N; ++j) {
            impossible[i][j] = false;
        }
    }
    ans = 0;
}

void input()
{
    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; i++)
    {
        // 순서 상관 X (양방향)
        scanf("%d %d", &ia, &ib);
        // 같이 있을 수 없는 재료 조합 표시
        impossible[ia][ib] = impossible[ib][ia] = true;
    }
}

bool isPossible(int target, int depth)
{
    for (int i = 0; i <= depth; i++)
    {
        if (impossible[target][selected[i]])
            return false;
    }
    return true;
}

void DFS(int idx, int depth)
{
    // 재료 개수와 상관없이 counting
    ans++;

    for (int i = idx; i < N; i++)
    {
        // 이미 선택한 재료인지 확인
        if (visited[i])
            continue;
        // 가능한 조합인지 확인
        if (!isPossible(i + 1, depth))
            continue;

        // 중복 조합 구현
        visited[i] = true;
        selected[depth] = i + 1;

        DFS(i, depth + 1);

        visited[i] = false;
        selected[depth] = 0;
    }
}

int main()
{
    // freopen("Input.txt", "r", stdin);
    scanf("%d", &TC);
    for (int tc = 1; tc <= TC; tc++)
    {
        init();
        input();
        DFS(0, 0);
        printf("#%d %d\n", tc, ans);
    }
    return 0;
}