백준 1497 기타콘서트 / python

문제 : 1497

풀이 point

N이 10으로 매우 작기 때문에 모든 조합을 확인해볼 수 있다. 조합을 생성하기 위해 백트래킹을 활용한다. 조합 생성 후 기타가 해당 곡을 연주할 수 있는지 없는지를 생성된 조합 내에서 확인해야한다. 이때 가장 좋은 것이 비트마스킹이다.

or 연산을 하면 1 or 0 : 1 이다. 이는 해당 조합에서 기타가 연주할 수 있는 곡인지를 확인하기에 매우 용이하다. 만약 비트마스킹이 없으면 조합 내에서도 또 다른 visit 배열을 만들어 확인해야한다.

ex)

조합 1
YYNN
NNYY
YNNN
이 경우 or 연산을 하면

YYYY가 된다. 매우 쉽게 구할 수 있다.

풀이 방법

visit 배열에 미리 비트마스킹 처리 한(YNNN 등의 값을 1000으로 표기한) 값을 집어넣고 백트래킹을 활용하여 조합을 구한다. 조합 내에서 or 연산을 통해 해당 조합이 모든 곡을 연주할 수 있는지 확인한다. 답은 가장 적은 기타의 수로 모든 곡을 연주하는 것이기 때문에 모든 조합을 확인하여 가장 적은 기타 조합으로 모든 곡을 칠 수 있는 조합을 알아내도록 한다.

풀이 코드

def back(depth, n, start, visit):
    global ans, maxSong
    
    if depth == n:
        currBit = 0
        for i in range(N):
            if visit[i]:
                currBit |= check[i]

        cnt = bin(currBit).count('1')
        
        if cnt > maxSong:
            maxSong = cnt
            ans = n
        return

    for i in range(start, N):
        if visit[i]:
            continue
        visit[i] = True
        back(depth+1, n, i+1, visit)
        visit[i] = False

N, M = map(int, input().split())

check = [0] * N

for i in range(N):
    guitar, ava = input().split()
    
    bit = 0
    for j in range(M):
        if ava[j] == 'Y':
            bit |= (1 << (M - 1 - j))
    check[i] = bit

ans = -1
maxSong = 0
for i in range(1, N + 1):
    visit = [False]*N
    back(0, i, 0, visit)
    if maxSong == M:
        break

print(ans if maxSong > 0 else -1)