알파코드(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
import sys
# sys.stdin = open("input.text", "rt")
sys.setrecursionlimit(10000)
ss = list(map(int, input()))
n = len(ss)
res = []
cnt = 0
def DFS(L):
global cnt
if L == n: #마지막까지. 종료조건 현재까지 알파벳 출력
cnt += 1
for x in res:
print(chr(64+x), end = "")
print()
else:
#각 숫자가 이제 1~26까지 가지 뻗는다는 것 이해하기 !
for i in range(1,27):
if ss[L] == i: #한자리인 경우
res.append(i)
DFS(L+1) #한자리니까 +1
res.pop() #백트랙킹하면 지워야지.
elif i>=10 and ss[L] == i // 10 and ss[L+1] == i%10: #두 자리수인데 각각 같은 경우
res.append(i)
DFS(L+2) #두자리니까 +2
res.pop()
ss.append(-1)
DFS(0)
print(cnt)코멘트
이 문제는 각 숫자가 1~26이 될 수 있다. 그렇기에 각 숫자별로 26가지의 상태트리가 뻗는다는 것을 이해할 수 있었어야 했다 ! + 각 숫자가 한 자리일때, 두 자리일 때 나눠서 생각할 수 있었어야 했다. 이걸 코드로 구현했어야 했는데 생각처럼 쉽지만은 않았다.
각 숫자마다 반복문을 1~26까지 돌면서 숫자를 찾아.
- 한 자리 숫자 먼저 찾을테니까 res에 저장 후 넘어감. DFS 진행
- 두 자리라면 (i>= 10) 두 자리 각각 비교해서 같으면 이제 찾은거야
- 그대로 두 자리 숫자 res에 넣어주고 +2만큼 넘어감
여기서 핵심은 가장 마지막 자리를 확인할 때 인덱스 오류가 뜰 수도 있다는 것이다.
가장 마지막 숫자가 2 이하인 경우 뒷자리를 확인하는데 그때 인덱스 오류로 에러가 뜬다. 이런 예외를 생각할 수 있었어야 했어!!!
- 그렇기에 에러가 안나기 위해 마지막 자리에 -1 추가해주면 확인해도 오류 안떠.
⚽ 숫자를 알파벳으로 출력해줘야 하니까 chr() 이용해서 출력 !!!
- chr(65) 가 "A"니까 이거 생각해서 작성해주면 끝.
⚽ 각 숫자별 1~26가지 뻗어나갈 수 있는... 이 문제 역시 부분집합 유형으로 상태트리 뻗어나가는 유형이었어. 근데 거기에 더해서 각 숫자가 한 자리로 갈지 두 자리로 갈지 여기서 한번 더 나뉘는 유형이었던 거지.
