[종만북] 문제: ALLERGY

게시 2025/01/17 업데이트 2025/03/06

By 정승우

12 분읽는 시간

문제

친구의 수 $n(1 \leq n \leq 50)$과 음식의 수 $m(1 \leq m \leq 50)$이 주어집니다.

$n$명 만큼 string 이름들이 주어집니다.

각 음식을 먹을 수 있는 string 이름 개수 $k$와

string 이름이 $k(1 \leq k \leq n)$개만큼 주어집니다.

모든 사람이 음식을 먹기 위해, 만들어야 할 최소한의 음식 수를 구하시오.

문제 링크

서론

가지치기와 정렬을 같이 활용해봅시다.

알고 가면 좋은 것

이 문제는 Set Cover라는 문제로, 계산이론쪽에서 유명한 NP-complete문제입니다.

문제를 처음 볼 때는 Greedy하게 생각해볼 수도 있으나, 결국 모든 입력에 대해 최적해를 찾아낼 수 없습니다.

결국 완전 탐색. 즉 음식을 $2^m$경우만큼 선택하는 함수를 작성해야하나, $2^{50}$은 상당히 무서운 숫자죠..

따라서 Greedy하게 풀지도 못하고, 완전탐색으로 풀어야 하나, 완전탐색시는 시간이 너무 걸립니다.

이 때 가지치기를 이용해봅시다. 가지치기를 잘 활용하기 위해서는 최적해에 가까운 값을 구해야합니다.

이를 위해서는 탐색의 방향을 좋게 바꿔야합니다.

이를 구현하기 쉽게 정렬을 이용합니다.

알고리즘 구상

최적화하기

앞서 말했듯이 $m$ 종류의 음식을 만드냐/만들지 않느냐로 분리하여 탐색하는건 무리입니다.

따라서 이 문제를 최적화하려 합니다.

생각할 수 있는 아이디어는 다음과 같습니다.

다음으로 만들 음식을 고를 때 아직 먹을 음식이 없는 친구들 중 가장 많은 사람이 먹을 수 있는 음식부터 시도
먹을 음식이 없는 친구들을 메모이제이션으로 해결

등.. 여러가지 최적화 기법이 있습니다.

최적화를 하기 위해 문제의 입력부터 다시 분석해보려고 합니다.

입력은 음식과 음식을 먹을 수 있는 친구들이 주어집니다.

하지만 친구들이 어떤 음식을 먹을 수 있는 지로 입력을 변형하면 어떨까요?

한술 더떠서, 친구들 중 음식을 먹을 수 있는 종류가 적은 친구들(편식쟁이들) 먼저 만족할 수 있게 음식을 선택하는 것은 어떨까요?

알고리즘 설계

알고리즘의 대략적인 순서는 다음과 같습니다.

데이터 초기화: 각 테스트 케이스마다 필요한 데이터를 초기화합니다.
- 각 친구의 이름을 정수 ID로 매핑하여 효율적으로 처리합니다. (StrToInt)
- 각 음식이 먹을 수 있는 친구들의 리스트를 저장합니다. (foodToFriendsList)
데이터 전처리 작업: 탐색을 최적화하기 위한 데이터를 준비합니다.
- 각 친구가 먹을 수 있는 음식들의 리스트를 생성합니다. (friendToFoodsList)
- 친구가 먹을 수 있는 음식 개수를 기준으로 오름차순 정렬하여 탐색 효율성을 높입니다. (FoodSizeSortedList)
백트래킹: 최소 음식 수를 탐색하는 백트래킹 알고리즘을 수행합니다.
- 현재 상태에서 최소 음식 수를 계산합니다.
- 가지치기를 통해 불필요한 탐색을 제거합니다.
- 재귀함수에서 친구가 음식을 먹을 수 있는 상태를 표현하기 위해 비트마스크를 이용합니다.
결과 계산: 모든 친구가 음식을 먹을 수 있는 경우, 최소 음식 개수를 best에 저장하고 출력합니다.

로 구상할 수 있습니다.

알고리즘 구현

사용한 STL들

앞서 설명한 알고리즘을 구현하기 위해 STL 여러 개를 선언합니다.

  
// friend의 이름을 0 1 2 3 ...n-1로 대응시킵니다.
unordered_map<string, int> StrToInt;
// 음식->친구
vector<vector<int>> foodToFriendsList;
// 친구->음식
vector<vector<int>> friendToFoodsList;
// 첫 번째 원소는 먹을 수 있는 음식의 개수,
// 두 번째 원소는 친구의 번호(0 ~ n-1)
vector<pair<int, int>> FoodSizeSortedList;

Init()

테스트케이스를 실행할 때마다, STL과 best값을 초기화합니다.

  
void init() {
    StrToInt.clear();
    foodToFriendsList.clear();
    friendToFoodsList.clear();
    FoodSizeSortedList.clear();
    best = 50;
}

InitData()

입력받은 데이터를 활용해 데이터를 전처리하는 함수입니다.

  
void initData() {
    friendToFoodsList.resize(n);
    // friendToFoodsList
    for (int food = 0; food < foodToFriendsList.size(); ++food) {
        for (int friendID : foodToFriendsList[food]) {
            friendToFoodsList[friendID].push_back(food);
        }
    }
    // FoodSizeSortedList
    for (int friendID = 0; friendID < friendToFoodsList.size(); ++friendID) {
        FoodSizeSortedList.push_back(
            {friendToFoodsList[friendID].size(), friendID});
    }
    sort(FoodSizeSortedList.begin(), FoodSizeSortedList.end());
}

Backtrack()

친구의 수는 $n(1 \leq n \leq 50)$이기 때문에, long long을 비트마스크로 이용해 풀 수 있습니다.

$best \leq count$이면 더 이상 탐색할 필요가 없으니 가지치기 합니다.
모든 친구가 음식을 먹을 수 있으면 $best$의 값을 갱신합니다.
그 외에 경우에 대해 재귀호출을 진행하면서 값을 탐색합니다.

  
void backtrack(long long fr, int index, int count) {
    // 기초적인 가지치기
    if (best <= count) return;

    // base case 모든 사람이 먹을 수 있는 음식 존재
    if (fr == ((1LL << n) - 1)) {
        best = min(count, best);
        return;
    }

    // 종료조건은 필요함.
    if (index == n) return;

    // recursive case
    int friendID = FoodSizeSortedList[index].second;

    // 채워져있는건 pass합니다.
    if (fr & (1LL << friendID)) backtrack(fr, index + 1, count);

    // 현재 FoodSizeSortedList[index]에 있는
    // friendID의 food들 중 무엇을 고를지 정합니다.
    for (int &food : friendToFoodsList[friendID]) {
        long long oldFr = fr;

        // 이후 이 food를 먹을 수 있는 friend의 비트마스크를 1로 채웁니다.
        for (int &friends : foodToFriendsList[food]) {
            fr |= (1LL << friends);
        }
        backtrack(fr, index + 1, count + 1);

        // 이후 이 food를 먹을 수 있는 friend의 비트마스크를 되돌립니다.
        fr = oldFr;
    }
}

사실 이 $backtrack$함수에는 결점이 있는데, $food$를 중복으로 골라서 $count$가 원래보다 더 크게 나올 수 있는 것입니다. 하지만, 가지치기 기법과 $best = min(count, best)$로 인해 이 결점은 운이 좋게 해결되었습니다.

Solve()

지금까지 만든 함수를 바탕으로 초기값을 설정하고 푸는 함수입니다.

  
int solve() {
    // 친구(0, n-1)이 먹을 수 있는 음식이 존재 시 1, 아니면 0
    long long FoodExist = 0;
    backtrack(FoodExist, 0, 0);
    return best;
}

최종 코드

여기에서 확인하세요!

알고리즘 개선

너무 코드가 긴 것 같은데..

구현은 잘 했고, 4ms라는 우수한 동작 시간을 얻어 좋았으나, 다만 코드의 길이가 너무 길었습니다.

다른 사람의 코드를 보며 어느 부분에서 단축할 수 있는지 분석하려고 합니다.

동작시간과, 작동 매커니즘은 비슷하나, 길이를 엄청나게 단축시킨 코드를 봅시다!

  
int T, N, M, ans;
long long Friends, canBeEaten[50], overHeu[50];
map<string, int> Map;
string s;

void init() {
	cin >> N >> M;
	Map.clear();
	for (int i = 0; i < N; i++) {
		cin >> s;
		Map[s] = i;
	}
	for (int i = 0; i < M; i++) {
		int t;
		cin >> t;
		canBeEaten[i] = 0;
		for (int j = 0; j < t; j++) {
			cin >> s;
			canBeEaten[i] |= (1ll << Map[s]);
		}
	}
	for (int i = 0; i < M; i++) {
		overHeu[i] = 0;
		for (int j = i + 1; j < M; j++) 
			overHeu[i] |= canBeEaten[j];
	}
	Friends = (1ll << N) - 1;
	ans = 51;
}

void search(int index, long long list, int cnt) {
	if (list == Friends) ans = ans > cnt ? cnt : ans;
	else if (cnt < ans - 1) {
		if ((list | canBeEaten[index]) != list) search(index + 1, list | canBeEaten[index], cnt + 1);
		if ((list | overHeu[index]) == Friends) search(index + 1, list, cnt);
	}
}

int main() {
	cin.sync_with_stdio(false);
	cin >> T;
	while (T--) {
		init();
		search(0, 0, 0);
		cout << ans << endl;
	}
}

bitmask를 잘 활용하기 위해 아예 친구들이 먹을 수 있는 음식의 종류를 bitmask처리해서 OR연산에 사용할 수 있도록 하는 게 인상깊었습니다.

알고리즘, 종만북

알고리즘 종만북