[ALLERGY] 문제 😊😊😊😊😊
집들이에 n 명의 친구를 초대하려고 합니다. 할 줄 아는 m 가지의 음식 중 무엇을 대접해야 할까를 고민하는데, 친구들은 각각 알러지 때문에 못 먹는 음식들이 있어서 아무 음식이나 해서는 안 됩니다. 만들 줄 아는 음식의 목록과, 해당 음식을 못 먹는 친구들의 목록이 다음과 같은 형태로 주어진다고 합시다.
각 친구가 먹을 수 있는 음식이 최소한 하나씩은 있도록 하려면 최소 몇 가지의 음식을 해야 할까요? 위 경우라면 다 같이 먹을 수 있는 음식이 없기 때문에 결국 두 가지 이상 음식을 해야 합니다. 피자와 탕수육, 혹은 잡채와 닭강정처럼 두 개 이상의 음식을 선택해야만 모두가 음식을 먹을 수 있지요. 친구들의 정보가 주어질 때 최소한 만들어야 하는 요리의 가지수를 계산하는 프로그램을 작성하세요.
[풀이]
문제 키 포인트는 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();
}
}
Comments