음식 메뉴 정하기 [c++]

// 음식 메뉴 정하기 
// N명의 친구들이 M가지 종류음식에 대해 먹을 수 있는지를 나타내는 리스트 friendEdibleList
// 모든 친구들이 식사를 하기 위해 최소한으로 만들어야할 음식의 갯수를 정하는 문제

#include <iostream>
#include <vector>

#define FOR(i, n) for(int i = 0; i < (n); i++)

using namespace std;

// 입력 예시 리스트
/*
4 6 
0 1 1 1 0 0 
0 0 0 0 1 1 
1 0 1 0 1 0 
1 1 0 0 0 1 
*/

// 출력 예시

// 2

const int INF = 987654321;
int n, m; // 친구 수 N, 음식 종류 M
// 고를 메뉴 벡터
vector<int> menu;
// 입력 값 받는 이차원 벡터
vector<vector<int>> friendEdibleList;

// 선정된 메뉴에 의해 모두가 식사를 할 수 있는지 확인하는 함수
bool CanEverybodyEat(const vector<int>& menu) {
    int menuSize = menu.size();
    int friendSize = n;
    bool edibleAll = true;
    // N명의 친구가 선정된 메뉴에 의해 식사를 할 수 있는지
    FOR(i, friendSize) {
        bool edible = false;
        FOR(j, menuSize) {
            edible = edible || friendEdibleList[i][menu[j]];
        }
        // 한 명이라도 식사를 할 수 없다면 false 리턴
        if (!edible) return false;
    }
    return edibleAll;
}


// food 번째 음식을 만들지 여부를 결정한다.
int selectMenu(vector<int>& menu, int food) {
    // base: 마지막 음식까지 모두 결정 했을 때
    if (food == m) {
        if(CanEverybodyEat(menu)) return menu.size();
        // 아무것도 못먹는 사람이 존재할 경우 INF 반환
        return INF;
    }

    // food번째 음식을 만들지 않을 경우의 답을 계산
    int ret = selectMenu(menu, food + 1);
    // food번째 음식을 만드는 경우의 답을 계산하여 더 작은 값을 취함
    menu.push_back(food);
    ret = min(ret, selectMenu(menu, food + 1));
    menu.pop_back();

    return ret;
}

int main()
{

    cin >> n >> m;

    // 행 크기 resize
    friendEdibleList.resize(n + 1);

    int a;
    FOR(i, n) {
        FOR(j, m) {
            cin >> a;
            friendEdibleList[i].push_back(a);
        }
    }

    cout << selectMenu(menu, 0);

    return 0;
}