알파코드(DFS)

철수와 영희는 서로의 비밀편지를 암호화해서 서로 주고받기로 했다. 그래서 서로 어떻게 암
호화를 할 것인지 의논을 하고 있다.
영희 : 우리 알파벳 A에는 1로, B에는 2로 이렇게 해서 Z에는 26을 할당하여 번호로 보내기
로 하자.
철수 : 정말 바보같은 생각이군!! 생각해 봐!! 만약 내가 “BEAN"을 너에게 보낸다면 그것을 암
호화하면 25114이잖아!! 그러면 이것을 다시 알파벳으로 복원할 때는 많은 방법이 존재하는
데 어떻게 할건데... 이것을 알파벳으로 바꾸면 BEAAD, YAAD, YAN, YKD 그리고 BEKD로
BEAN말고도 5가지나 더 있군.
당신은 위와 같은 영희의 방법으로 암호화된 코드가 주어지면 그것을 알파벳으로 복원하는데
얼마나 많은 방법인 있는지 구하세요.

▣ 입력설명

첫 번째 줄에 숫자로 암호화된 코드가 입력된다. (코드는 0으로 시작하지는 않는다, 코드의 길
이는 최대 50이다) 0이 입력되면 입력종료를 의미한다.

▣ 출력설명

입력된 코드를 알파벳으로 복원하는데 몇 가지의 방법이 있는지 각 경우를 출력한다. 그 가지
수도 출력한다. 단어의 출력은 사전순으로 출력한다.

▣ 입력예제 1

25114
▣ 출력예제 1
BEAAD
BEAN
BEKD
YAAD
YAN
YKD
6

풀이

• 1 ~26까지가 알파벳이므로 1자리수로 끊거나 2자리수로 끊으면 됩니다.
• ex) 25114 -> 25/1/1/4, 2/5/1/1/4 .... 등

import sys
sys.stdin=open("input.txt", "r")
def DFS(L, P):
    global cnt
    if L==n:
        cnt+=1
        for j in range(P):
            print(chr(res[j]+64), end='')
        print()
    else:
        for i in range(1, 27):
            if code[L]==i:
                res[P]=i
                DFS(L+1, P+1)
            elif i>=10 and code[L]==i//10 and code[L+1]==i%10:
                res[P]=i
                DFS(L+2, P+1)

if __name__=="__main__":
    code=list(map(int, input()))
    n=len(code)
    code.insert(n, -1)
    res=[0]*(n+3)
    cnt=0
    DFS(0, 0)
    print(cnt)

• 위와 같은 방식은 숫자를 for문으로 1~26까지 반복문을 실행해서 code에 맞는 i의 값을 res 리스트에 넣고 chr 내장함수를 통해서 출력하는 방법입니다.
• 이 경우 반복문을 for문과 dfs 방식을 사용하므로 아래와 같은 방식보다 시간복잡도가 조금 더 높고 로직이 복잡합니다.

from string import ascii_uppercase


def dfs(a, alpha):
    global cnt, lst
    if a >= m:
        lst.append(alpha)
        cnt += 1
    else:
        if int(n[a]) == 0:
            return
        dfs(a + 1, alpha + alpha_up[int(n[a]) - 1])
        val = int(n[a:a+2])
        if a < m - 1 and val <= 26:
            dfs(a + 2, alpha + alpha_up[val - 1])


alpha_up = ascii_uppercase
n = input()
m = len(n)
cnt = 0
lst = []
dfs(0, "")
lst.sort()
print("\n".join(lst) + "\n" + str(cnt))

• 이 경우는 어차피 알파벳은 1자리수로 끊거나 2자리수로만 끊기므로 두 가지의 경우만 고려한 코드입니다.
• 이 코드는 string 라이브러리에서 알파벳 대문자들을 모두 가져오고 그에 해당하는 것들을 모두 리스트에 넣어준 다음 리스트와 개수를 출력하게 만들었습니다.
• 그리고 0이 들어오면 입력 종료이므로 이 부분을 확실하게 체크해야합니다.