Algorithm - 알파코드(DFS)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[알파코드(DFS)]

 

철수와 영희는 서로의 비밀편지를 암호화해서 서로 주고받기로 했다. 그래서 서로 어떻게 암호화를 할 것인지 의논을 하고 있다.

 

영희 :

우리 알파벳 A에는 1로, B에는 2로 해서 Z에는 26을 할당하고 번호로 보내기로 하자.

 

철수 :

생각해봐!! 만약 내가 "BEAN"을 너에게 보낸다면 그것을 암호화하면 "25114"이잖아? 그러면 이것을 다시 알파벳으로 복원할 때는 많은 경우의 수가 존재하게 돼.. 실제로 "25114"을 알파벳으로 바꾸면 "BEAAD", "YAAD", "YAN", "YKD", "BEKD"로 "BEAN" 말고도 5가지의 경우의 수가 더 있음을 알 수 있어!!

 

위의 예시를 참고하여, 영희의 방법으로 암호화된 숫자코드가 주어지면 그것을 알파벳으로 복원하는데 얼마나 많은 방법이 존재하는지를 출력하는 프로그램을 작성하시오.

 

 

*입력 설명

첫 번째 줄에 숫자로 암호화된 코드가 입력된다.

단, 코드는 0으로 시작하지 않으며 코드의 길이는 최대 25이다.

또한, 0이 입력되면 입력종료를 의미한다.

 

*출력 설명

입력된 코드를 알파벳으로 복원하는데 몇 가지의 방법이 존재하는지 각 경우를 출력한다.

마지막 줄에는 총 경우의 수를 출력한다.

단, 단어의 출력은 사전순으로 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_61.txt', 'rt')

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)
    
'''
출력 :
BEAAD
BEAN
BEKD
YAAD
YAN
YKD
6

'''

 

input_61.txt(입력)

25114

 

 

중요내용

1. 변수 res는 복원가능한 알파벳에 대응되는 숫자를 저장하기 위한 리스트 자료형이다.
2. 변수 n은 상태트리에서 탐색을 종료하는 시점을 의미한다.
3. 상태트리의 가지는 총 26개이며, 이는 알파벳의 개수를 의미한다. (오직 대문자만 고려함)
4. DFS() 함수의 인자 L은 리스트 code의 인덱스 번호이자 동시에 알파벳에 대응되는 숫자를 탐색할 때 적용되는 자리수로 사용된다.
5. DFS() 함수의 인자 P는 리스트 res의 인덱스 번호이자 동시에 복원가능한 알파벳에 대응되는 숫자를 저장할 때 사용된다.
6. if 절의 조건 " code[L] == i "와 DFS(L+1, P+1)는 리스트 code에 존재하는 숫자에 대응되는 알파벳을 탐색할 때, 오직 한 자리의 숫자를 고려하겠다는 의미이다.
7. if 절의 조건 " i >= 10 and code[L] == i // 10 and code[L+1] == i % 10 "과 DFS(L+2, P+1)는 리스트 code에 존재하는 숫자에 대응되는 알파벳을 탐색할 때, 오직 두 자리의 숫자를 고려하겠다는 의미이다.
8. code.insert(n, -1)는 리스트 code의 인덱스 번호 n자리에 -1 값을 넣는 코드로, 이는 두 자리 숫자에 대응되는 알파벳을 탐색할 때 발생할 수 있는 에러를 방지하기 위함이다. (ex. list index out of range)
9. chr()는 숫자를 알파벳으로 변환해주는 함수이므로, 숫자 65가 대문자 A라는 것을 고려하여 " chr(res[j] + 64) "로 코드를 작성한 것이다.