[백준 #1062]: 가르침(python)

백준#3085:사탕게임

- 브루트포스, 비트마스킹

import sys
from itertools import combinations


input_index,letter_index  = map(int,sys.stdin.readline().strip().split())
# k 가 5보다 작으면 어떤 언어도 배울 수 없음
if letter_index < 5:
    print(0)
    exit()
# k 가 26이면 모든 언어를 배울 수 있음
elif letter_index == 26:
    print(input_index)
    exit()

word_list = [set(sys.stdin.readline().strip()).difference('a', 'c', 'i', 't', 'n') for _ in range(input_index)]
alpa_list={chr(i + 97): i for i in range(26)}

song=0
for i in combinations([i for i in range(26) if chr(i + 97) not in ['a', 'c', 'i', 't', 'n']],letter_index-5):
    count=0
    combi_bit=0
    for j in i:
        combi_bit |= 1 << j
    for j in word_list:
        word_bit=0
        for k in j:
            word_bit|= 1 << alpa_list[k]
        if combi_bit | word_bit == combi_bit:
            count += 1
    song=max(song,count)
print(song)

해당 문제는 브루트 포스 방식으로 해결할 수 있다. 하지만 시간 초과를 해결하기위해 비트마스킹 기법을 사용해야한다.
combinations을 사용하여 a,c,i,t,n을 제외한 문자들로 이루어진 모든 경우의 수를 만들고 비트마스킹 기법을 이용하여 포함관계에 있는지 확인해주면 된다.

- 백트래킹, DFS

import sys

input_index, letter_index = map(int, input().split())

# k 가 5보다 작으면 어떤 언어도 배울 수 없음
if letter_index < 5:
    print(0)
    exit()
# k 가 26이면 모든 언어를 배울 수 있음
elif letter_index == 26:
    print(input_index)
    exit()
    
song = 0
words = [set(sys.stdin.readline().strip()) for _ in range(input_index)]
learn = [0] * 26
# 적어도 언어 하나는 배우기위해 a,c,i,n,t 는 무조건 배워야함
for c in ('a', 'c', 'i', 'n', 't'):
    learn[ord(c) - ord('a')] = 1
def dfs(idx, cnt):
    global song
    if cnt == letter_index - 5:
        count = 0
        for word in words:
            check = True
            for w in word:
                if not learn[ord(w) - ord('a')]:
                    check = False
                    break
            if check:
                count += 1
        song = max(song, count)
        return

    for i in range(idx, 26):
        if not learn[i]:
            learn[i] = True
            dfs(i, cnt + 1)
            learn[i] = False
dfs(0, 0)
print(song)

해당 문제는 dfs를 활용한 백트래킹으로도 해결 할 수 있다. 깊이 우선 탐색을 활용하여 접근하고 만약 if cnt == letter_index - 5: 조건이 만족할 경우 포함관계에 있는지 확인해 보면된다.