문제링크 입니다

[ALLERGY] 문제 😊😊😊😊😊

집들이에 n 명의 친구를 초대하려고 합니다. 할 줄 아는 m 가지의 음식 중 무엇을 대접해야 할까를 고민하는데, 친구들은 각각 알러지 때문에 못 먹는 음식들이 있어서 아무 음식이나 해서는 안 됩니다. 만들 줄 아는 음식의 목록과, 해당 음식을 못 먹는 친구들의 목록이 다음과 같은 형태로 주어진다고 합시다.

ALLERGY

각 친구가 먹을 수 있는 음식이 최소한 하나씩은 있도록 하려면 최소 몇 가지의 음식을 해야 할까요? 위 경우라면 다 같이 먹을 수 있는 음식이 없기 때문에 결국 두 가지 이상 음식을 해야 합니다. 피자와 탕수육, 혹은 잡채와 닭강정처럼 두 개 이상의 음식을 선택해야만 모두가 음식을 먹을 수 있지요. 친구들의 정보가 주어질 때 최소한 만들어야 하는 요리의 가지수를 계산하는 프로그램을 작성하세요.

[풀이]

문제 키 포인트는 i번쨰 친구가 먹을 수 있는 음식의 집합과 i번 음식을 먹을 수 있는 친구들의 집합을 구현해야 했다.
이를 위해 map을 사용하여 친구 이름을 key로 하고 Index를 값으로 input을 받아왔다.

search() 는 항상 모든 친구가 먹을 음식이 없는 음식이 있는 조합을 찾아내고 한 번 호출 될때마다 항상 음식을 한가지 가져온다.

입력

입력의 첫 줄에는 테스트 케이스의 수 T (T <= 50 ) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 친구의 수 n (1 <= n <= 50) 과 할 줄 아는 음식의 수 m (1 <= m <= 50) 이 주어집니다. 다음 줄에는 n 개의 문자열로 각 친구의 이름이 주어집니다. 친구의 이름은 10 자 이하의 알파벳 소문자로만 구성된 문자열입니다. 그 후 m 줄에 하나씩 각 음식에 대한 정보가 주어집니다. 각 음식에 대한 정보는 해당 음식을 먹을 수 있는 친구의 수와 각 친구의 이름으로 주어집니다.

모든 친구는 하나 이상의 음식을 먹을 수 있다고 가정해도 좋습니다.

출력

각 테스트 케이스마다 한 줄에 만들어야 할 최소의 음식 수를 출력합니다.

입력 예제

2
4 6
cl bom dara minzy
2 dara minzy
2 cl minzy
2 cl dara
1 cl
2 bom dara
2 bom minzy
10 7
a b c d e f g h i j
6 a c d h i j
3 a d i
7 a c f g h i j
3 b d g
5 b c f h i
4 b e g j
5 b c g h i

출력 예제

2
3

전체 코드는 다음과 같습니다.

//
//  ALLERGY.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/11/01.
//

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
ifstream fin("ALLERGY.txt");

int friendNum;
int foodNum;
// i번 친구가 먹을 수 있는 음식의 집합
vector<int> canEat[50];
// i번 음식을 먹을 수 있는 친구들의 집합
vector<int> eaters[50];
const int INF = 987654321;
int best;
void clear();

// edible 지금까지 고른 음식중, i 번 친구가 먹을 수 있는 음식의 수
// chosen : 지금까지 선택한 음식의 수
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]]--;
        }
    }

}

int main(){
    int test_case;
    fin >> test_case;
    for(int test =0; test<test_case; test++){
        best = INF;
        fin >> friendNum >> foodNum;
        map<string, int> index;
        for(int i=0; i< friendNum; i++){
            string name;
            fin >> name;
            index[name] = i;
        }
        for(int i=0; i<foodNum; i++){
            int num;
            fin >> num;
            for(int j=0; j<num; j++){
                string temp;
                fin >> temp;
                eaters[i].push_back(index[temp]);
                canEat[index[temp]].push_back(i);
            }
        }
        vector<int> edible(friendNum,0);
        search(edible,0);
        cout << best << endl;
        clear();
    }

}

void clear(){
    for(int i=0; i<friendNum; i++){
        canEat[i].clear();
    }
    for(int i=0; i<foodNum; i++){
        eaters[i].clear();
    }
}

ALLERGY

Comments