[ 백준 ][ 골드5 ] 11578번 - 팀원 모집 ( Python 파이썬 )

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

11578번: 팀원 모집

 

코드

---

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를 저장한다.

 

여기까지하면 이제 어떤 학생들로 팀을 구성해야 최소로 모든 문제를 해결할 수 있을지 고민했다.

처음에는 가장 많은 문제를 해결할 수 있는 팀원은 무조건 저장하고 문제 해결 수에 따라 정렬하여 탐색해야 하나 싶었다.

하지만 가장 많은 문제를 해결하더라도 그 팀원이 해결하지 못한 문제를 해결할 수 있는 팀원이 없다면 답이 없기 때문에 이건 무조건 완전탐색이라는 생각이 들었다.

 

입력으로 받은 배열의 순서를 바꾸지 않고 그대로 두고 인덱스별로 탐색했다.

깊이 우선 탐색으로 현재 인덱스에 위치한 학생을 팀에 포함시킬지 안시킬지 두 갈래로 나누어 탐색하였고 현재까지 저장한 팀원들로 모든 문제가 해결가능해지면 팀원의 수를 정답으로 저장했다.