개인공부용123 프로그래밍 블로그

AlgoSpot) ALLERGY 본문

알고리즘문제

AlgoSpot) ALLERGY

개인공부용123 2017. 1. 22. 19:59

문제 : https://algospot.com/judge/problem/read/ALLERGY


사람마다 먹을 수있는 음식이 있는데 최소한의 음식만 준비해서 모든 사람이 음식을 먹을수있게 하는 문제입니다.


이 문제를 해결할때 불필요한 낭비를 하지않기위해 음식을 못먹은 사람을 찾고 그 사람이 먹을 수있는 음식을 대입해가면서 최소로 준비할수있는 음식의 수를 찾는 방법을 이용했습니다. 

간단한 가지치기로 현재까지 찾은 최저값보다 클 경우는 재귀를 더이상 수행하지 않게 처리했습니다.




#include <iostream>
#include <vector>
#include <string>
#include <map> 

using namespace std;

int n, m; // 친구 음식
int best; // 가장 좋은경우
vector foods[50]; // 음식을 먹을수있는 사람이 원소
vector person[50]; // 사람이 먹을수있는 음식이 원소

void Search(vector& edible,int choosen) {
	if (choosen == best) return; // 최적의 경우를 넘어갈경우는 없앰

	int first_person = 0;

	while (first_person < n && edible[first_person] > 0) ++first_person; // 아무것도 못먹은 사람을 찾음

	if (first_person == n) { // 모두 다먹었을경우
		best = choosen;
		return;
	}

	for (int i = 0; i < person[first_person].size(); ++i) { // 해당하는 사람이 먹을수있는 음식만 표시
		int food = person[first_person][i]; // 해당하는 사람이 먹을 수있는 음식
		
		for (int j = 0; j < foods[food].size(); ++j) ++edible[foods[food][j]]; // 음식을 먹었다고 표시
		Search(edible, choosen + 1);
		for (int j = 0; j < foods[food].size(); ++j) --edible[foods[food][j]]; // 원상태로 복귀
	}

	return;
}

int main() {
	ios::sync_with_stdio(false);

	int C;
	cin >> C;

	while (C--) {
		cin >> n >> m;
		best = m;

		map match;	
		for (int i = 0; i < n; ++i) {
			string name;
			cin >> name;
			match[name] = i;
		}
		
		
		for (int food = 0; food < m; ++food) { // 음식 별 사람
			int num;
			cin >> num;
			for (int j = 0; j < num; ++j) {
				string name;
				cin >> name;
				foods[food].push_back(match[name]);
				person[match[name]].push_back(food);
			}
		}

		vector edible(n, 0);
		Search(edible, 0);

		cout << best << endl; // 최적해 출력

		for (int i = 0; i < m; ++i) foods[i].clear();
		for (int i = 0; i < n; ++i) person[i].clear();
		match.clear();
		edible.clear();
	}

	return 0;
}


저작자표시

'알고리즘문제' 카테고리의 다른 글

AlgoSpot) ARCTIC  (0) 2017.02.03
AlgoSpot) DARPA  (0) 2017.01.31
AlgoSpot) QUADTREE  (1) 2017.01.21
AlgoSpot) STRJOIN  (0) 2017.01.16
AlgoSpot) LUNCHBOX  (12) 2017.01.14
'알고리즘문제' Related Articles more