파이썬 알고리즘 060 | 알파코드(DFS) ***

60. 알파코드(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,2,1 로 나눌 수 있는 경우를 제시하고 주어진 숫자 중에서 26넘는 거는 제외해서 세고 싶었다. 그래서 일단 1,2,1 로 나눠지는 모든 경우의 수는 구했는데, 이걸로 어떻게 주어진 숫자 (예제에선 2 5 1 1 4) 를 나눠볼지 몰랐다
  =>
  [1, 1, 1, 1, 1][1, 1, 1, 2]
  [1, 1, 2, 1][1, 2, 1, 1]
  [1, 2, 2][2, 1, 1, 1]
  [2, 1, 2][2, 2, 1]

def dfs(x,s) : 
    global cnt
    if s>len(k) :
        return
    if s==len(k):
        print(v)
    else:
        v.append(1)
        dfs(x+1, s+1)
        v.pop()
        v.append(2)
        dfs(x+1, s+2)
        v.pop()
if __name__=='__main__' :
    v=[]
    cnt=0
    k=(str(input()))
    dfs(0,0)
    print(cnt)
    

(2) 두번째 시도

• res 라는 리스트 만들고 k의 일정 인덱스부터 일정 인덱스 까지 넣어주기
  ==> 이것도 index out of range오류 걸려서 계속 잘못 나옴

def dfs(x,s) : 
    global cnt
    if x>len(k) :
        return
    if s==k :
        print(res)
    else:
        res[x]=k[s:s+1]
        dfs(x+1, s+1)
        res.pop()
        res[x]=k[s:s+2]
        dfs(x+1, s+2)
        res.pop()
if __name__=='__main__' :
    cnt=0
    k=str(input())
    res=[]
    dfs(0,0)
    print(cnt)

(3) 설명 듣고 구현 => however, 실패

==>어째서 s==len(k)인 케이스가 하나도 없다고 뜨는지를 모르겠음
====> k=list(map(int, str(input()))) 이라고 했으면 k안에 담긴 애들은 리스트로 담겨있음
======>그리고 만약 이 상태에서 k[s:s+1]하면 리스트니깐 당연히 저 i랑 같은 경우가 존재하지 않는다..이 바보얏

def dfs(x,s) : 
    global cnt
    if s>len(k):
        return
    if s==len(k) :
        cnt+=1
        print(res)
        return
    else:
        for i in range(1,27) :
            if i ==k[s:s+1]:
                res.append(i)
                dfs(x+1,s+1)
                res.pop()
            if i ==k[s:s+2]:
                res.append(i)
                dfs(x+1,s+2)
                res.pop()
if __name__=='__main__' :
    cnt=0
    k=list(map(int, str(input())))
    res=[]
    dfs(0,0)
    print(cnt) #0이라고 출력될 뿐, res도 낭지 않고

(4) 리스트랑 정수 비교 안된다는 거 감안하고 다시 구현했는데도 실패..
나중에 원인 파악해보자

def dfs(x,s) : 
    global cnt
    if x==len(k) :
        print(res)
        return
    else:
        for i in range(1,27) :
            if i ==int(k[s:s+1]):
                res.append(i)
                dfs(x+1,s+1)
                res.pop()
            elif i ==int(k[s:s+2]):
                res.append(i)
                dfs(x+1,s+2)
                res.pop()

if __name__=='__main__' : 
    cnt=0 
    k=str(input()) 
    k+='0'
    res=[] 
    dfs(0,0)
    print(cnt)

(5) - 드디어 (4) 코드를 수정해서 정답 출력해냄! 다 왔었는데 활용을 못한 점이 아쉽 ㅠㅠ if s==len(k)로 설정했어야 하는데, x==len(k)라고 했었음
그리고 res안에 들어가는 경우의 수 다 구했으니깐 이걸 for로 하나하나 꺼내고 64 더해서 문자로 바꿔주면 된다===> 흐앙 근데 다른 예제들에서 오류 있음 ㅠㅠ 다시 수정필요..

def dfs(x,s) : 
    global cnt
    if s==len(k) :
        for i in res:
            print(chr(i+64), end='')
        cnt+=1
        print()
        return
    else:
        for i in range(1,27) :
            if i ==int(k[s:s+1]):
                res.append(i)
                dfs(x+1,s+1)
                res.pop()
            elif i ==int(k[s:s+2]):
                res.append(i)
                dfs(x+1,s+2)
                res.pop()

if __name__=='__main__' : 
    cnt=0 
    k=str(input())
    res=[] 
    dfs(0,0)
    print(cnt)
    

<풀이>

• (1) 풀이
  ===>반성 point
  for i in range(1,27) :
  if i==k[s] : #이렇게 k[s] 가 아니고 k[x]
  res[x]=i #여긴 res[x]
  else :
  if i >=10 and i==k[s] :
  res[x]=i
  dfs(x+1, s+2)

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)

-(2) 영상 보면서 따라쓴 풀이..
처음에 if x==len(k) 라고 설정했었는데 나중에 insert 값 때문에 len(k)가 잘못 지정되어서 계속 잘못 나왔었음

• 또한 k[x]=i 인지 k[s]=i 인지 계속 헷갈렸음
• insert 또 중요, 만약 42222 이게 입력값이었으면
  마지막에 2를 읽을 때 얘가 i//10==2이면 elif i>=10 and k[x]==i//10 and k[x+1]==i%10: 이게 성립할텐데 더 이상 k[x+1]이 존재하지 않아서 인덱스 에러 out of range 뜰 것임 => 그래서 k의 맨마지막에 -1을 넣어줌으로써 저게 성립하지 않게 한다

<반성점>

• 계에속 상태트리를 못 구현하고 있다,, 다음에 복습할 때 꼭 암기하면서 바로 구현할 수 있게 하고 다른 DFS문제들도 많이 풀어보자

• 다 잘 했었는데도 x,s를 헷갈렸다. 앞으로는 코드를 세울 때 명확하게 비교를 하고 범위를 잡자

<배운 점>

• ord(문자) : 아스키 코드를 반환해줌
• chr(숫자) : 숫자에 맞는 아스키 코드를 반환해줌

아스키 넘버

• a : 97 - z : 122
• A : 65 - Z : 90

<2회독 내 풀이> - 까먹은 부분 하나 존재

list a에 맨 마지막에 '-1'을 삽입해주어야 함
elif i>=10 and i//10==a[x] and i%10==a[x+1]:
여기서 숫자가 20~까지 있기 때문에 만약 a 리스트가
2로 끝났으면 2를 i//10 (i가 20대인) 으로 인식하고
a[x+1]을 찾으려 할텐데 없어서 오류가 뜰 것이다
그렇기 때문에 리스트a의 마지막에 -1을 넣어서
저게 성립하지 않게 해줘야 함

def dfs(x) :
    global cnt
    if x==aa:
        cnt+=1
        for i in res:
            if i>0:
                print(chr(i+64),end='')
        print()
    else : 
        for i in range(27) :
            if i<10 and a[x]==i:
                res[x]=i
                dfs(x+1)
                res[x]=0
            elif i>=10 and i//10==a[x] and i%10==a[x+1]:
                res[x]=i
                dfs(x+2)
                res[x]=0

if __name__=='__main__' :
    cnt=0
    a=list(map(int, str(input())))
    aa=len(a)
    res=[0]*(aa+1)
    dfs(0)
print(cnt)