11578 팀원 모집

BOJ::11578 팀원 모집

https://www.acmicpc.net/problem/11578

백트래킹을 이용하여 풀었다.

#include <stdio.h>
using namespace std;
 
int n, m,cnt,min;
int map[11][11];
int check[11];
bool flag;
 
//모든 문제를 풀 수 있는지 체크
bool isOK() {
    for (int i = 1; i <= n; i++) {
        if (check[i] == 0) {
            return false;
        }
    }
    return true;
}
//백트래킹
void dfs(int v) {
    cnt++;
    for (int i = 1; i <= n; i++) {
        if (map[v][i] == 1) {
            check[i]++;
        }
    }
    //모든 문제를 풀 수 있으면서 가장 적은 인원인 경우
    if (isOK()) {
        flag = true;
        if (min > cnt) {
            min = cnt;
        }
    }
    else {
        for (int i = v + 1; i <= m; i++) {
            dfs(i);
        }
    }
 
    cnt--;
    for (int i = 1; i <= n; i++) {
        if (map[v][i] == 1) {
            check[i]--;
        }
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int x;
        scanf("%d", &x);
        for (int j = 0; j < x; j++) {
            int y;
            scanf("%d", &y);
            map[i][y] = 1;
        }
    }
 
    min = 100000;
    flag = false;
    for (int i = 1; i <= n; i++) {
        cnt = 0;
        dfs(i);
    }
 
    if (flag) {
        printf("%d\n", min);
    }
    else {
        printf("-1\n");
    }
}