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

분류 : 브루트포스 + 자료구조

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

풀이

1번부터 N번까지의 문제를 모두 풀 수 있는 최소한의 팀원수를 구하는 문제이다.

각 팀원은 자신이 풀 수 있는 문제 번호 리스트를 가지고 있다. 팀원은 M명이며, 문제를 모두 풀 수 있는 팀원의 최소 수를 구해야한다.

A = [list(map(int, input().split()))[1:] for _ in range(M)]
A = [set(a) for a in A]

각 팀원이 자신이 풀 수 있는 문제 번호들을 입력받는다.

list(map(int, input().split()))[1:] 에서 [1:] 부터 시작하는 이유는 첫 번째 숫자는 개수이므로 무시한다.

set(a)로 변환해서 나중에 합집한 연산을 쉽게 수행하도록 만든다.

예시는 다음과 같다.

4 3
2 1 2
2 3 4
1 2

A = [{1, 2}, {3, 4}, {2}]

answer = -1
for n in range(1, M + 1) :
    found = False

1명부터 M명까지 조합을 시도하며, n명이 모이면 모든 문제 (1 ~ N)를 커버할 수 있는지 확인한다.

    for combination in combinations(A, n) :
        U = set()
        for a in combination :
            U |= a

combination은 팀원 조합(set들의 리스트)를 나타내며 U |= a는 U = U.union(a)와 같다.

즉, 팀원들이 커버 가능한 문제들을 모두 합친다.

        if len(list(U)) == N :
            found = True
            break

U의 길이가 N이면 모든 문제를 커버했다는 뜻이므로, 더이상 탐색할 필요가 없어 break를 걸어준다.

코드

# 백준 11578 - 팀원 모집
# 분류 : 브루트포스 + set 자료구조

from itertools import combinations

N, M = map(int, input().split())
A = [list(map(int, input().split()))[1:] for _ in range(M)]
A = [set(a) for a in A]

answer = -1
for n in range(1, M + 1) :
    found = False
    for combination in combinations(A, n) :
        U = set()
        for a in combination :
            U |= a
        if len(list(U)) == N :
            found = True
            break

    if found : 
        answer = n
        break

print(answer)