11578 팀원 모집

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

11578번: 팀원 모집

백트래킹은 아니고 브루트 포스 문제 같다.

전체 경우의 수를 다 해봐야 하니 DFS로 전체 탐색

 

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

#define initialize(x, y) memset(x, y, sizeof(x));

int N, M, cnt, min_cnt;
int std_solve[11][11];
int solve[11];
bool flag;

bool isSolve() {
	for (int i = 1; i <= N; i++) {
		if (solve[i] == 0) {
			return false;
		}
	}
	return true;
}

void dfs(int u) {
	cnt++;
	for (int i = 1; i <= N; i++) {
		if (std_solve[u][i] == 1) {
			solve[i]++;
		}
	}

	if (isSolve()) {
		flag = true;
		if (cnt < min_cnt) {
			min_cnt = cnt;
		}
	}
	else {
		for (int i = u + 1; i <= M; i++) {
			dfs(i);
		}
	}

	cnt--;
	for (int i = 1; i <= N; i++) {
		if (std_solve[u][i] == 1) {
			solve[i]--;
		}
	}
}

int main() {
	int O, input;
	min_cnt = 100;
	cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		cin >> O;
		for (int j = 1; j <= O; j++) {
			cin >> input;
			std_solve[i][input] = 1;
		}
	}

	for (int i = 1; i <= N; i++) {
		cnt = 0;
		dfs(i);
	}

	if (flag) {
		cout << min_cnt;
	}
	else {
		cout << -1;
	}
}

어떻게 풀어야 할지 감이 안 잡혀서 검색의 힘을 빌려버렸다..

많이 풀면 바로바로 풀 수 있겠지 *_*

점점 DFS의 신세계에 빠지는 중..