[BOJ] 1062 가르침

보실 분이 있으실지는 모르겠지만 열심히 구상한 테스트케이스들입니다..!

# k값과 문자열을 구성하는 알파벳 개수가 같을 때 제대로 출력되는지 확인,

1 5
antatica

답 : 1

# 문자열을 구성하는 알파벳 개수보다 k값이 작은 경우 제대로 출력되는지 확인,

1 4
antatica

답 : 0

# 문자열을 구성하는 알파벳 개수보다 k값이 큰 경우 제대로 출력되는지 확인, ★ 이거때매..

1 10
antatica

답 : 1

# 제대로 쪼개졌는지 확인,

3 5
antatica
antaaatica
antaaaaatica

답 : 3

# a,i,t,n,c 제대로 빠지고 잘 작동하는지 확인

3 5
antaxxxxtica
antaltica
antaltica

답 :0

# 위와 같음

3 6
antaxxxxtica
antaltica
antaltica

답 : 2

아마 이 문제는 일단 백트래킹으로 모든 경우를 얻은 뒤 비교하는 방식으로 풀어야겠다고 생각했습니다. 늘 그렇듯 골드정도의 문제면 백트래킹과 하나씩은 섞여있는 것 같습니다. 그 하나의 방법으로 직접 해보지는 않았지만 브루트포스로도 풀 수 있을 것이라 생각합니다. 그러나 저는 꼭 한번 써보고싶던 비트마스킹을 사용해서 이 문제를 풀어보았습니다.

백트래킹으로 얻을 수 있는 최악의 경우의 수를 일단 계산해보았습니다.

26개의 알파벳 중에서 절반인 13개를 선택하는 경우의 수

알파벳 중에 anta와 tica에 공통적인 5개를 제외하고 마찬가지로 절반인 10개를 선택하는 경우의 수

많이 차이날 것이라 생각은 했는데 그 이상으로 차이가 심해서 꼭 a,i,t,c,n을 빼주고 백트래킹을 해주어야 할 것 같습니다.

파이썬은 아마 별 상관 없겠지만, 마찬가지로 비트마스킹에 사용할 값의 최댓값도 크게 차이가 났습니다. 빼주지 않는다면 알파벳 마지막 값인 z는 2**25 약 3천만, 빼준다면 2**20 약 100만으로 큰 차이가 있습니다.

일단 알파벳과 알파벳에 대응하는 값을 가진 배열을 만들어주었습니다.

alphabet={'b': 0, 'd': 1, 'e': 2, 'f': 3, 'g': 4, 'h': 5, 'j': 6,\
          'k': 7, 'l': 8, 'm': 9, 'o': 10, 'p': 11, 'q': 12, 'r': 13,\
          's': 14, 'u': 15, 'v': 16, 'w': 17, 'x': 18, 'y': 19, 'z': 20,\
          'a':-1,'n':-1,'t':-1,'c':-1,'i':-1}

아까 빼줄 알파벳들을 만나면 넘겨주기위해 그 알파벳들에 대응하는 값들에는 -1을 넣어주었습니다, 빼주는 것만 없었다면 chr을 이용해서 훨씬 이쁜 코드가 나왔을 텐데 너무 더러워진게 아쉽습니다.

일단 입력을 받은 뒤 알파벳에 대응하는 수 만큼의 제곱을 한 2의 합을 저장한 뒤 mask라는 배열에 넣어주었습니다. 이 때 만약 같은 배열이 있을 수 있으므로 딕셔너리를 이용해 해당 값이 나온 횟수도 저장해주었습니다. 또한 입력에 들어온 값들을 중복을 허용하지 않도록 able에 저장시키고 마지막에 list로 바꿔주었습니다. 그리고 백트래킹에 사용할 방문을 확인할 배열 able도 만들어주었습니다.

ans=0
mask={}
able={}
mx_len=0

for i in range(n):
    word=set(input().rstrip())
    bi=0
    for i in word:
        if alphabet[i]!=-1:
            bi+=2**alphabet[i]
            able[i]=1
    try:
        mask[bi]+=1
    except:
        mask[bi]=1

able=list(able)
vi=[0]*len(able)

다음은 mask 내의 값들과 백트래킹으로 얻은 값을 비교해주고, 완전한 단어를 만들 수 있는 경우의 최댓값을 업데이트 해줄 함수를 구현해주었습니다.

def check(len_k_bin):
    global ans
    cnt=0
    for j in mask:
        if j&len_k_bin==j:
            cnt+=mask[j]
    ans=max(cnt,ans)

이걸 구현하면서 아 비트마스킹이 이런 거구나를 느꼈습니다...mask안에 들어있는 값과 전달받은 값을 and연산해서 mask안에 들어있는 값이 나온다면 그 값을 입력받은 횟수만큼 cnt에 더해주고, mask안에 들어있는 모든 값을 연산한 최종 cnt값과 답을 저장할 변수 ans를 max연산을 해주었습니다.

남은 것은 이제 백트래킹으로 check에 전달해줄 값을 만드는 것이므로 간단하게 구현해주었습니다.

def dfs(w,idx,recur):
    if recur==k:
        check(w)
        return ans
    for i in range(idx,len(able)):
        if vi[i]==0:
            vi[i]=1
            dfs(w+2**alphabet[able[i]],i+1,recur+1)
            vi[i]=0

 k는 5개 이상이여야 하고 빼줘야할 알파벳들을 제외한 채로 진행하므로 k-=5가 된 상태의 k입니다. 만약 k가 able(제외한 알파벳들을 제외한 입력받은 알파벳들)보다 큰 경우 입력받은 모든 값이 가능하므로 출력할 값은 입력받은 횟수 n이 됩니다. 만약 k가 5보다 작은 경우 어떠한 단어도 만들 수 없으므로 답은 0입니다. 이것은 dfs 내부에서 k가 음수가 되고, recur은 0부터 증가하기만 하므로 ans의 값을 업데이트해주는 check함수가 실행될 일이 없고, 따라서 ans의 맨 처음 값인 0이 출력됩니다.

최종 코드입니다.

from sys import stdin
input=stdin.readline

n,k=map(int,input().split())
k-=5
alphabet={'b': 0, 'd': 1, 'e': 2, 'f': 3, 'g': 4, 'h': 5, 'j': 6,\
          'k': 7, 'l': 8, 'm': 9, 'o': 10, 'p': 11, 'q': 12, 'r': 13,\
          's': 14, 'u': 15, 'v': 16, 'w': 17, 'x': 18, 'y': 19, 'z': 20,\
          'a':-1,'n':-1,'t':-1,'c':-1,'i':-1}

ans=0
mask={}
able={}
mx_len=0

for i in range(n):
    word=set(input().rstrip())
    bi=0
    for i in word:
        if alphabet[i]!=-1:
            bi+=2**alphabet[i]
            able[i]=1
    try:
        mask[bi]+=1
    except:
        mask[bi]=1

able=list(able)
vi=[0]*len(able)

def check(len_k_bin):
    global ans
    cnt=0
    for j in mask:
        if j&len_k_bin==j:
            cnt+=mask[j]
    ans=max(cnt,ans)


def dfs(w,idx,recur):
    if recur==k:
        check(w)
        return ans
    for i in range(idx,len(able)):
        if vi[i]==0:
            vi[i]=1
            dfs(w+2**alphabet[able[i]],i+1,recur+1)
            vi[i]=0

dfs(0,0,0)
print(n if len(able)<k else ans)