[BOJ] 백준 11578 팀원 모집 - Python/Java

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

11578번: 팀원 모집

해설

조합을 이용한 완전탐색, 그리고 비트마스킹을 이용해서 풀이한 문제입니다.

 

맨 처음에 각 친구가 알고 있는 문제를 비트로 표현한 후, 이를 배열(prob)에 담아주는데요. 예를 들어 1번 친구가 3, 4, 5번 문제를 알고 있다면 0b11100(2) = 4+8+12 = 24 라는 숫자가 배열의 1번 인덱스에 들어가게 됩니다. 그러면 결과적으로 각 배열의 값은 해당 친구가 풀 수 있는 문제를 저장하게 됩니다.

 

이런 식으로 배열을 생성한 뒤 최소 1명의 친구부터 최대 m명의 친구까지를 선택해봅니다. 이러한 조합 선택에서 파이썬은 itertools 라이브러리를 이용하면 되지만 자바같은 경우에는 combination을 백트랙킹으로 구현해서 써야 합니다.

 

조합을 이용해 K명의 친구가 선택된 상황이라면, 위에서 각 친구가 풀 수 있는 문제를 저장했던 배열(prob)에서 뽑아와서 서로 OR('|') 연산을 해줍니다. 그러면 최종적인 결과는 K명의 친구들을 통해 풀 수 있는 문제가 모두 기록된 비트값이 생성되게 됩니다.

 

그리고 이 비트값과 총 문제 수(N)을 비교하여 전체문제를 다 풀 수 있는지 확인하고, 다 풀 수 있다면 그 즉시 K(필요한 친구의 수)를 출력해주면 됩니다.

 

풀이는 아래와 같습니다.

풀이 - 파이썬

from itertools import combinations as C
n, m = map(int, input().split())

prob = []
# 각 친구가 풀 수 있는 문제를 비트화해서 저장한다.
for i in range(m):
    temp = 0b00000000000
    for p in list(map(int, input().split()))[1:]:
        temp |= (1 << p)
    prob.append(temp)

answer = -1
# k명의 친구를 선택해서 모든 문제를 풀 수 있는지 확인한다.
for k in range(m+1):
    solved = list(C(prob, k))
    stop = False
    for solve in solved:
        temp = 0b0000000000
        for s in solve:
            temp |= s
        # 모든 문제를 풀 수 있으면 종료 
        if temp == 2 ** (n+1) - 2:
            answer = k
            stop = True
            break
    if stop:
        break            
print(answer)

풀이 - 자바

package PS;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class B_11578 {
    static int n, m;
    static int[] prob;
    static boolean find;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        prob = new int[m];  // 각 학생이 아는 문제를 비트화하여 저장하는 배열
        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int o = Integer.parseInt(st.nextToken()); // 각 학생이 알고 있는 문제의 수
            for(int j = 0; j < o; j++){
                int p = Integer.parseInt(st.nextToken());
                prob[i] |= (1 << p);
            }
        }

        // k명의 친구를 선택해서 모든 문제를 풀 수 있는지 확인한다.
        for(int k = 1; k <= m; k++){
            boolean[] visited = new boolean[m];
            combination(prob, visited, 0, m, k);
            if(find){
                System.out.println(k);
                break;
            }
        }
        if(!find){
            System.out.println(-1);
        }
    }

    public static void combination(int[] arr, boolean[] visited, int start, int x, int r){
        if(r == 0){
            int temp = 0;
            for(int i = 0; i < x; i++){
                if(visited[i]){
                    temp |= arr[i];
                }
            }
            // 현재 조합으로 모든 문제를 풀 수 있으면 Flag를 true로 바꾼다.
            if(temp == (int)(Math.pow(2, (n+1)) - 2)){
                find = true;
            }
        }
        for(int i = start; i < x; i++){
            visited[i] = true;
            combination(arr, visited, i+1, x, r-1);
            visited[i] = false;
        }
    }
}