[문자열] Python - 1062번, 가르침

import sys
input = sys.stdin.readline


def dfs(idx, cnt):
    global maxCntReadable
    if cnt == K-5:  # Base Case
        cntReadable = 0
        for word in words:
            isReadable = True
            for c in word:
                if isLearned[ord(c)-ord('a')] == False:
                    isReadable = False
                    break
            if isReadable:
                cntReadable += 1
        maxCntReadable = max(maxCntReadable, cntReadable)
        return

    for i in range(idx, 26):  # Recursive Case
        if isLearned[i] == False:
            isLearned[i] = True
            dfs(i, cnt+1)
            isLearned[i] = False


N, K = map(int, input().split())
words = [input().strip() for _ in range(N)]

if K < 5:
    print(0)
else:
    isLearned = [False]*26

    for c in ('a', 'c', 'i', 'n', 't'):
        isLearned[ord(c)-ord('a')] = True

    maxCntReadable = -1
    dfs(0, 0)
    print(maxCntReadable)

 

 

dfs의 Recursive Case에서 알파벳을 돌며 배웠는지 조사를 하는데, 이 때 백트레킹을 썼으며, 또 다른 특징으로는, 파라미터를 (i, cnt+1)으로 줬다는 것이다. 첫째 파라미터가 의미하는 바는, 조사한 것의 이전의 알파벳은 조사하지 않는다는 것이며, 두번째 파라미터가 의미하는 바는, 지금까지 알파벳을 cnt번 추가했다는 것이다.

이것이 Base Case로 연결되는데, cnt가 K-5일 때가 조건이다. a, c, i, n, t는 이미 고려하였으니, 만약 8개의 알파벳을 가르쳐야한다면 3번을 더 가르쳐야하는 것이므로 K-5이다. 입력된 words를 돌면서, 현재의 isLearned와 비교를 해가면서 각 word가 전부 다 배운 알파벳으로 이루어져 있어서 읽기가 가능하다면 isReadable을 1만큼 증가시킨다. 그렇게, 현재의 isLearned에 대해서 words 탐색을 마치면 max 연산으로 최댓값을 넣어준다.