[ 백준 ][ 골드5 ] 11578번 - 팀원 모집 ( Python 파이썬 )
링크 : https://www.acmicpc.net/problem/11578
11578번: 팀원 모집
3번 학생과 4번 학생을 선택하면 1번부터 5번까지 모든 문제를 풀 수 있는 팀을 만들 수 있다. 1번, 2번, 4번 학생을 선택해도 모든 문제를 다 풀 수 있지만 팀원의 수가 3명이라 답이 될 수 없다.
www.acmicpc.net
코드
def DFS(idx,cnt,total):
global answer
if total == target:
answer = min(answer,cnt)
return
if idx >= m:
return
DFS(idx+1, cnt+1, total | students[idx])
DFS(idx+1, cnt, total)
n,m = map(int,input().split())
students = [0] * m
target = 0
for i in range(n):
target |= (1 << i)
for i in range(m):
q, *arr = map(int,input().split())
tmp = 0 if students[i] == 0 else students[i]
for p in arr:
tmp |= (1 << (p-1))
students[i] = tmp
answer = 1e9
DFS(0,0,0)
print(answer if answer < 1e9 else -1)
풀이
오랜만에 풀어보는 비트마스킹 문제인데 생각보다 쉽게 풀렸고 메모리, 시간제한을 고려한 순위에서 3등이 되어서 아주 기쁘다.

이 문제가 비트마스킹인 이유는 학생이 풀어낼 수 있는 문제의 종류를 저장하기 애매해서이다.
입력으로 주어지는 풀어낼 수 있는 문제의 배열을 모두 저장하고 가지고 돌아다니면서 탐색하게 되면 시간초과, 메모리 초과 둘 중 하나를 벗어날 수 없다.
따라서 비트마스킹으로 문제별로 풀어낼 수 있으면 1, 아니면 0으로 저장하여 정수하나로 압축시켜서 저장한다.
예를 들어, 한 학생이 1,3,4번 문제를 풀 수 있다면 0b1101 = 29를 저장한다.
여기까지하면 이제 어떤 학생들로 팀을 구성해야 최소로 모든 문제를 해결할 수 있을지 고민했다.
처음에는 가장 많은 문제를 해결할 수 있는 팀원은 무조건 저장하고 문제 해결 수에 따라 정렬하여 탐색해야 하나 싶었다.
하지만 가장 많은 문제를 해결하더라도 그 팀원이 해결하지 못한 문제를 해결할 수 있는 팀원이 없다면 답이 없기 때문에 이건 무조건 완전탐색이라는 생각이 들었다.
입력으로 받은 배열의 순서를 바꾸지 않고 그대로 두고 인덱스별로 탐색했다.
깊이 우선 탐색으로 현재 인덱스에 위치한 학생을 팀에 포함시킬지 안시킬지 두 갈래로 나누어 탐색하였고 현재까지 저장한 팀원들로 모든 문제가 해결가능해지면 팀원의 수를 정답으로 저장했다.