[백준 11578번] 팀원 모집 - JAVA

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

11578번: 팀원 모집

<풀이>

사용한 알고리즘 : 비트마스킹, 백트래킹

 

※ 풀이 전략 

 1. 학생 개인이 풀 수 있는 문제를 2진수로 나타낸다.

     풀 수 있는 문제는 1, 풀 수 없는 문제는 0으로 표기한다.

     ex)  예로 1번 학생이 총 5문제 중 2, 3, 5 번을 풀 수 있다고 한다면

            10110 (2) = 22 이다.(오른쪽부터 1번 문제이고, 맨 왼쪽 비트가 5번 문제를 나타낸다.)

  

 2. 백트래킹을 기법을 이용하여 트리 형식의 순회를 하되, 부모 노드에서 이미 지나쳤던 노드는

     다시 방문하지 않도록 한다.

     또한 모든 문제를 풀 수 있는 경우에 참여한 학생 수를 구하고, 그 중 가작 적은 수를 저장뒤 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static List<Integer> list = new LinkedList<Integer>();
	static int initialVal;
	static int minimumVal=6;
	static int[] canSol;
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		
		initialVal=(int)(Math.pow(2, N))-1;
		canSol= new int[M+1];
		for(int i=1;i<M+1;++i) {
			st = new StringTokenizer(br.readLine());
			int solNum=Integer.parseInt(st.nextToken());
			for(int j=0;j<solNum;++j) {
				canSol[i]|=1<<(Integer.parseInt(st.nextToken())-1);
			}
		}
		recur(M);
		if(minimumVal==6) {System.out.println(-1); return;}
		System.out.println(minimumVal);
	}
	
	public static void recur(int M) {
		int result=0;
		for(int i=0;i<list.size();++i){
			result|=list.get(i);
		}
		if(result==initialVal) {
			if(minimumVal>list.size()) minimumVal=list.size();
			return;
		}
		for(int i=1;i<M+1;++i) {
			if(!list.contains(canSol[i]))
			{
				list.add(canSol[i]);
				recur(M);
				list.remove(list.size()-1);
			}
		}
	}
}