알파코드 (DFS)

생성일: 2022년 2월 12일 오후 4:11

구현 코드

# 알파코드 (DFS)
import sys
#sys.stdin = open("in2.txt", "rt")

def numToChr(num):
    return chr(num+64)

def DFS(L, pre):
    global cnt
    if L == len(code):
        if pre == 0:
            for x in res:
                if x != "":
                    print(x, end='')
            print()
            cnt += 1
    else:
        if pre == 0 and code[L] != 0:
            #채택
            res[L] = numToChr(code[L])
            DFS(L+1, 0)
            res[L] = ""
            #채택x
            DFS(L+1, code[L])
        else:
            if 10*pre+code[L] > 26:
                pass
            else:
                if pre != 0:
                    #무조건 채택
                    res[L] = numToChr(10*pre+code[L])
                    DFS(L+1, 0)
                    res[L] = ""

if __name__ == "__main__":
    code = list(map(int,list(input())))
    res = [""]*len(code)
    cnt = 0
    DFS(0, 0)
    print(cnt)

모범 답안

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)

차이점

• 내가 구현한 DFS함수에서는 pre 파라미터를 통해 L번째 숫자를 즉시 문자로 변환하지 않고 다음으로 넘겨서 L+1번째 숫자와 합쳐서 문자로 변환하는 경우의 수를 구했다.
• 모범 답안에서는 1부터 26까지의 수(문자로 치면 A~Z)를 반복문을 통해 돌면서 code의 L번째 숫자와 비교한다.
• 이때 i가 L번째 숫자와 같다면 res에 추가(한자리 수만 채택), 만약 i가 두자리 수 이면 L번째 숫자와 첫째 자리를비교하고 L+1번째 숫자와 둘째자리를 비교하여 같으면 res에 추가하고 다음 파라미터로 두칸을 넘긴다(두자리 숫자를 채택했기 때문)
• 예를들어, code가 25114이면 L=0일때, i가 2가 되었을 때 res에 B를 추가하고 i가 25가 되었을 때 L번째 숫자인 2와 L+1번째 숫자인 5가 합쳐진 수와 같기 때문에 res에 Y(25를 문자로 바꾼 것)를 추가하고 두칸을 넘겨서 재귀함수를 호출한다.