[조합 탐색] ALLERGY 알러지가 심한 친구들

1. 완전 탐색(시간초과, 잘못된 구현)

 

이 문제는 각 친구들이 먹을 수 있는 음식이 하나라도 먹을 수 있게 하는

최소한의 메뉴를 선정하는 문제이다.

 

이 문제는 다음과 같이 완전 탐색할 수 있다.

 

- 친구들을 기준으로 탐색

- 음식들을 기준으로 탐색

 

모든 친구들이 먹을 수 있는게 하나라도 있어야하므로

친구들을 기준으로 탐색하는게 더욱 구현이 직관적일 것이다.

 

코드는 다음과 같다.

#include <iostream>
#include <map>
#include <utility>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
 
std::vector<std::string> names;
std::vector<std::vector<int>> menuToName;
std::vector<std::vector<int>> nameToMenu;
bool visited[50] = {false,};
int best;
 
int find(std::string& tmp, int menu)
{
    for(int i = 0; i < names.size(); i++)
    {
        if(tmp.compare(names[i]) == 0){
            nameToMenu[i].push_back(menu);
            return i;
        }
    }
    return -1;
}
 
void visitMenu(std::vector<int>& selected, int menu, bool it)
{
    if(it) selected.push_back(menu);
    else selected.pop_back();
    for(int i = 0; i < menuToName[menu].size(); i++)
        visited[menuToName[menu][i]] = it;
}
 
int allergy(std::vector<int>& selected, int i)
{
    int count = 0;
    
    if (selected.size() > best)
        return INT32_MAX;
    
    if(i == nameToMenu.size()-1) 
        return selected.size();
 
    if(visited[i] != false)
        return allergy(selected, i+1);
 
    for(int j = 0; j < nameToMenu[i].size(); j++)
    {
        visitMenu(selected, nameToMenu[i][j], true);
        best = std::min<int>(best, allergy(selected, i+1));
        visitMenu(selected, nameToMenu[i][j], false);
    }
 
    return best;
}
 
int main()
{
    int testCase, n, m, tmp;
    std::string str;
 
    std::cin>>testCase;
    for(int i = 0; i < testCase; i++)
    {
        best = INT32_MAX;
 
        names.clear(); menuToName.clear(); nameToMenu.clear();
        memset(visited, false, sizeof visited);
        std::cin>>n>>m;
        names.resize(n); menuToName.resize(m); nameToMenu.resize(n);
 
        for(int j = 0; j < n; j++)
            std::cin>>names[j];
 
        for(int j = 0; j < m; j++)
        {
            std::cin>>tmp;
            menuToName[j].resize(tmp);
            for(int k = 0; k < tmp; k++)
            {
                std::cin>>str;
                menuToName[j][k] = find(str, j);;
            }
        }
        std::vector<int> selected;
        std::cout<<allergy(selected, 0)<<"\n";
    }
}

 

가지치기를 어느정도 했음에도 불구하고

이 코드로는 문제를 시간안에 해결할 수 없다.

 

또 다른 문제는 visit를 bool으로 나타낸것이다.

visit는 해당 친구가 음식을 먹을 수 있는게 있는지를 나타내야하는게 아니라

음식을 먹을 수 있는 개수를 나타내야한다.

 

그 이유는 업데이트 될때 pop을 하게되면 이전 선택에서 먹을 수 있었다고 표시한게

false가 되어버려 잘못된 결과 값이 나오게 된다.

 

2. 순서를 바꿔보자 (탐욕법)

 

데이터들의 처리 순서를 한번 바꿔보자

 

어느 순서로 친구들을 처리해야 더 빠르게 실행될까?

 

가장 까다로운 친구 먼저 처리하는게 아마 최적해를 가져다 줄꺼같다.

 

그 이유는 선택지가 많은 친구들은

다른 선택에 의해 자동으로 체크될 확률이 높기 때문이다.

 

코드는 다음과 같다.

 

#include <iostream>
#include <map>
#include <utility>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
 
std::vector<std::string> names;
std::vector<std::vector<int>> menuToName;
std::vector<std::vector<int>> nameToMenu;
std::vector<int> smallEat;
int visited[50] = {0,};
int testCase, n, m, best;
 
bool cmp(const int &a, const int& b)
{
    int A = nameToMenu[a].size();
    int B = nameToMenu[b].size();
    return A > B;
}
 
void visitMenu(int menu, int it)
{
    for(int i = 0; i < menuToName[menu].size(); i++)
        visited[menuToName[menu][i]] += it;
}
 
void allergy(int chosen, int index)
{
    if( 0 > index) {
        if(best > chosen)
            best = chosen;
        return;
    }
    int i = smallEat[index];
    if (chosen > best)
        return;
 
    if(visited[i] > 0)
        return allergy(chosen, index - 1);
    for(int j = 0; j < nameToMenu[i].size(); j++)
    {
        visitMenu(nameToMenu[i][j], 1);
        allergy(chosen + 1, index -1);
        visitMenu(nameToMenu[i][j], -1);
    }
    return;
}
int find(std::string& tmp, int menu)
{
    for(int i = 0; i < names.size(); i++)
    {
        if(tmp.compare(names[i]) == 0){
            nameToMenu[i].push_back(menu);
            return i;
        }
    }
}
int main()
{
    std::string str;
    std::cin>>testCase;
    
    for(int i = 0; i < testCase; i++)
    {
        best = INT32_MAX;
 
        names.clear(); menuToName.clear(); nameToMenu.clear(), smallEat.clear();
        memset(visited, 0, sizeof visited);
        std::cin>>n>>m;
        names.resize(n); menuToName.resize(m); nameToMenu.resize(n);
     
        for(int j = 0; j < n; j++)
        {
            std::cin>>str;
            names[j] = str;
        }
        for(int j = 0; j < m; j++)
        {
            int tmp;
            std::cin>>tmp;
            for(int k = 0; k < tmp; k++)
            {
                std::cin>>str;
                menuToName[j].push_back(find(str, j));
            }
        }
        for(int j = 0; j < n; j++) smallEat.push_back(j);
        sort(smallEat.begin(), smallEat.end(), cmp);
        allergy(0, n-1);
        std::cout<<best<<"\n";
    }
}

 

3. 반성

완전 탐색으로 풀고 지금까지의 최적해 보다 나빠지면 그만두게 수정한뒤

시간초과가 나와서 책의 해설을 참고하여 코드를 수정하였음에도 불구하고

코드를 수정하는 과정에서 실수 하나가 있었다.

 

그것은 바로 visited를 int로 타입을 변환하는 과정에서

visitMenu에서 더하고 빼는 인자인 it의 타입을 bool로 썼던 것이다.

 

이러한 실수를 눈치못채고 시간을 많이 소비하게 되었다.

앞으로 코드를 수정할 때 조심하자

 

4. NP문제

 

이 문제는 집합 덮개(set cover)라고 부르는 문제로 

계산 이론쪽에서는 가장 유명한 NP 완비 문제 중 하나이다.

 

5. 더 최적화하기.

 

음식을 선택할 때 가장 많은 사람이 먹을 수 있는 음식부터 시도.

 

 

ALLERGY