algospot ALLERGY

문제 링크입니다: https://algospot.com/judge/problem/read/ALLERGY

slowSearch와 search의 코드 구성은 크게 다르지 않습니다.

하지만 탐색순서가 다르기 때문에 다음과 같은 차이가 생겼습니다.

1. search()는 항상 모든 친구가 먹을 음식이 있는 조합만을 찾아냅니다. 

   하지만 slowSearch()는 마지막 조각까지 결정한 뒤에도 배고픈 친구가 남는 경우들도 모두 탐색하게됩니다.

2. search()는 한 번 호출될 때마다 항상 음식을 하나 하게 됩니다.

   (즉, 음식을 한다는 말은 음식이 필요한 친구가 반드시 있다는 의미)

   반면 slowSearch()는 음식을 하지 않고도 재귀호출을 할 수 있습니다.(반드시 필요하지 않은 음식을 만드는 경우도 있다)

#include <iostream>

#include <string>

#include <map>

#include <algorithm>

#include <vector>

using namespace std;

 

int friendNum, foodNum;

//canEat[i]: i번 친구가 먹을 수 있는 음식의 집합

//eaters[i]= i번 음식을 먹을 수 있는 친구들의 번호

vector<int> canEat[50], eaters[50];

int best;

 

/*

//food:이번에 고려해야 할 음식의 번호

//edible: 지금까지 고른 음식 중 i번 친구가 먹을 수 있는 음식의 수

//chosen:지금까지 고른 음식의 수

void slowSearch(int food, vector<int> &edible, int chosen)

{

        //간단한 가지치기

        if (chosen >= best)

               return;

        //기저 사례:모든 음식에 대해 만들지 여부를 결정했으면

        //모든 친구가 음식을 먹을 수 있는지 확인하고 그렇다면 최적해 갱신

        if (food == foodNum)

        {

               if (find(edible.begin(), edible.end(), 0) == edible.end())

                       best = chosen;

               return;

        }

        //food를 만들지 않는 경우

        slowSearch(food + 1, edible, chosen);

        //food를 만드는 경우

        for (int j = 0; j < eaters[food].size(); j++)

               edible[eaters[food][j]]++;

        slowSearch(food, edible, chosen + 1);

        for (int j = 0; j < eaters[food].size(); j++)

               edible[eaters[food][j]]--;

}

*/

 

//chosen:지금까지 선택한 음식의 수

//edible[i]:지금까지 고른 음식 중 i번 친구가 먹을 수 있는 음식의 수

void search(vector<int> &edible, int chosen)

{

        //간단한 가지치기

        if (chosen >= best)

               return;

        //아직 먹을 음식이 없는 첫번째 친구를 찾는다

        int first = 0;

        while (first < friendNum && edible[first]>0)

               first++;

        //모든 친구가 먹을 음식이 있는 경우 종료

        if (first == friendNum)

        {

               best = chosen;

               return;

        }

        //이 친구가 먹을 수 있는 음식을 하나 만든다

        for (int i = 0; i < canEat[first].size(); i++)

        {

               int food = canEat[first][i];

               for (int j = 0; j < eaters[food].size(); j++)

                       edible[eaters[food][j]]++;

               search(edible, chosen + 1);

               for (int j = 0; j < eaters[food].size(); j++)

                       edible[eaters[food][j]]--;

        }

}

 

//배열 초기화

void clear(void)

{

        for (int j = 0; j < foodNum; j++)

               eaters[j].clear();

        for (int j = 0; j < friendNum; j++)

               canEat[j].clear();

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case < 1 || test_case>50)

               exit(-1);

 

        for (int i = 0; i < test_case; i++)

        {

               cin >> friendNum >> foodNum;

               if (friendNum < 1 || friendNum>50 || foodNum < 1 || foodNum>50)

                       exit(-1);

               best = foodNum;

 

               map<string, int> index; //canEat과 eaters 벡터에 추가할 때 필요

               for (int j = 0; j < friendNum; j++)

               {

                       string name;

                       cin >> name;

                       index[name] = j; //해당이름을 가진 사람은 j번째 인덱스이다

               }

 

               for (int j = 0; j < foodNum; j++)

               {

                       int people;

                       cin >> people;

                       for (int k = 0; k < people; k++)

                       {

                              string name;

                              cin >> name;

                              //j번 음식을 먹을 수 있는 사람들

                              eaters[j].push_back(index[name]);

                              //현재 이 사람이 먹을 수 있는 음식 목록에 j번 음식 추가

                              canEat[index[name]].push_back(j);

                       }

               }

               vector<int> edible(friendNum, 0); //아직 음식을 고르지 않았으므로 모두 0

               search(edible, 0);

               cout << best << endl;

               clear();

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략