11.5_알러지가 심한 친구들_ALLERGY

문제 설명

algospot.com :: ALLERGY

• n명의 친구를 초대한다.
• m가지의 음식 중 무엇을 대접할지를 고른다.
• 만들 줄 아는 음식의 목록과, 해당 음식을 못 먹는 친구들의 목록이 주어진다.

=> 각 친구가 먹을 수 있는 음식이 최소 하나씩은 있도록 하는 음식의 최소 개수를 출력하기

 

문제 풀이

자료구조 고르기

나는 이 문제에 비트마스킹을 이용했다.

각 요리마다 먹을 수 있는 친구의 수를 저장하는데,

주어지는 친구의 수(n)가 최대 50명이므로

64비트의 Long Long 자료형을 이용하면 비트마스킹으로 표현이 가능하다.

 

※ a, b, c, d 친구가 있을 때 c와 a가 먹을 수 있는 음식 : 0101(2)

친구	a	b	c	d
index	0	1	2	3
음식(비트)	1	0	1	0

이 때, 주의할 점은 C++에서 비트 연산을 수행할 때 32비트 연산을 수행하기 때문에,

1 << 45 와 같은 연산을 수행할때는

• (long long)1 << 45
• 1LL << 45
• 1i64 << 45

와 같이 형변환을 시켜주어야 한다.(몰라서 고생함...ㅠ)

 

 

음식 수 줄이기

각 음식 정보를 비트마스킹을 이용해서 저장할 때,

다른 음식과 비교해서 한 음식이 다른 음식을 대체할 수 있다면 해당 음식을 삭제해주었다.

두 음식을 or 연산한 결과로 두 음식 중 하나와 값이 동일하다면 대체할 수 있음을 의미하고 덮어씌웠다.

 

가지치기

음식을 고를 때,

1. 고른 음식의 수가 최솟값보다 작다면 리턴하기
2. 해당 음식을 고름으로써 음식을 먹을 수 있는 사람의 수가 늘어난다면 선택하기

과 같은 과정을 추가하여 더 빠르게 답을 찾을 수 있도록 가지치기를 수행했다.

 

문제 풀이 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>

using namespace std;

int n, m, minCnt;
long long success;
long long foods[50];
char friends[50][10];

// 친구 index 반환
int findFriendsIndex(char* name) {
	for (int i = 0; i < n; ++i) {
		bool find = true;
		for (int j = 0; j < 10; ++j) {
			if (name[j] == '\0' && friends[i][j] == '\0')
				break;
			if (name[j] != friends[i][j]) {
				find = false;
				break;
			}
		}
		if (find)
			return i;
	}
}

// 음식 고르기
void choiceFood(int index, long long sum, int cnt) {
	// 고른 음식의 수가 최솟값보다 커지면
	if (cnt >= minCnt)
		return;
    	// 답을 찾았다면
	if (sum == success) {
		minCnt = cnt;
		return;
	}
    	// 음식을 전부 확인했다면
	if (index == m)
		return;

	// i번째 음식을 고름으로써 먹을 수 있는 사람이 늘어난다면
	if ((sum | foods[index]) > sum) {
		choiceFood(index + 1, sum | foods[index], cnt + 1);
	}
	choiceFood(index + 1, sum, cnt);
}

int main() {
	int T;
	cin >> T;
	for (int tc = 1; tc <= T; ++tc) {
		cin >> n >> m;
		minCnt = m;
		memset(foods, 0, sizeof(foods));
        	// 성공하는 경우 = 모든 친구가 먹는 경우 = n-1개의 비트가 모두 1인 경우
		success = ((long long)1 << n) - 1;
		for (int i = 0; i < n; ++i) {
			cin >> friends[i];
		}
		for (int i = 0; i < m; ++i) {
			int cnt;
			cin >> cnt;
			for (int j = 0; j < cnt; ++j) {
				char name[10];
				cin >> name;
				int index = findFriendsIndex(name);
            	    	// index 번째 친구가 먹을 수 있음을 표기
				foods[i] = foods[i] | ((long long)1 << index);
			}

			// 한쪽이 다른 한쪽을 대신할 수 있는 음식 제거
			for (int j = 0; j < i; ++j) {
				if ((foods[i] | foods[j]) == foods[i]) {	// j가 i에 포함 
					foods[j] = foods[i];
					foods[i] = 0;
					--m;
					--i;
					break;
				}
				else if ((foods[i] | foods[j]) == foods[j]) {	// i가 j에 포함
					foods[i] = 0;
					--m;
					--i;
					break;
				}
			}
		}

		choiceFood(0, 0, 0);
		cout << minCnt << endl;
	}
	return 0;
}