[1일 1알고] G5 5175 문제없는 문제

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

 

해당 문제는 간단한 dfs, 백트래킹 문제입니다.

N,M이 20이하로 굉장히 작은 범위이며, 정답을 찾기 위해서는 모든 조합을 탐색해야하기 때문에 조합을 탐색하는 방법을 그대로 사용하면 됩니다. 

 

조합으로 표현하면 (N)C(1~N)을 모두 경우의 수로 하여 이 중 M을 충족하는 지 확인해야합니다.

 

일반적으로 생각해보면 bool vector혹은 array를 통해 모든 알고리즘을 사용하는지 확인하며 백트래킹 할 수 있겠지만

위에서 말한 것 처럼 N과 M의 범위가 매우 작기 때문에 bool vector 대신 비트마스킹을 사용해볼 수 있습니다.

 

예를 들어 알고리즘 1과 2를 사용한다면 11, 1과 3을 사용한다면 101과 같이 저장하면 됩니다.

최대 20자리이기 때문에 int 자료형에 충분히 들어갑니다.

---

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <math.h>

using namespace std;
vector<int> v;
int algoset = 0;
int resultsize = 21;
ostringstream oss;
ostringstream ans;
int M, N;
void dfs(int idx, int result, vector<int>& stack, int size);
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int K;
    cin >> K;
    for (int k = 0; k < K; ++k)
    {
        cin >> M >> N;
        v = vector<int>(N, 0);
        algoset = pow(2, M) - 1;
        resultsize = 21;
        cin.ignore();
        for (int i = 0; i < N; ++i)
        {
            string line;
            getline(cin, line);
            stringstream ss(line);

            int num;
            while (ss >> num)
            {
                v[i] += 1 << (num - 1);
            }
        }

        oss << "Data Set " << k + 1 << ": ";
        vector<int> stack;
        dfs(0, 0, stack, 0);
        oss << ans.str();
        oss << "\n\n";
    }
    cout << oss.str();
    return 0;
}

void dfs(int idx, int result, vector<int>& stack, int size)
{
    if (size >= resultsize)
        return;
    if (algoset == result)
    {
        ans.str("");
        ans.clear();
        for (auto elem : stack)
        {
            char ch = 'A' + elem;
            ans << ch << ' ';
        }
        resultsize = stack.size();
        return;
    }

    for (int i = idx; i < N; ++i)
    {
        stack.push_back(i);
        dfs(i + 1, result | v[i], stack, size + 1);
        stack.pop_back();
    }
}

idx는 현재 탐색하는 인덱스, result는 비트마스킹한 값, stack은 결과에 필요한 누적 index, size는 최소 크기의 문제를 가려내기 위한 값입니다.

 

앞 인덱스부터 탐색하는 조합이라면 자연스럽게 사전순으로 결과가 저장됩니다.