[Algorithm] ๐Ÿšฉ ์•ŒํŒŒ์ฝ”๋“œ (DFS)

6010 ๋‹จ์–ด algorithmalgorithm


๊ฐ€์ง€ = 1~26 (A~Z)
๋…ธ๋“œ - ์ž…๋ ฅ ๋ฆฌ์ŠคํŠธ์˜ ์ธ๋ฑ์Šค

code.insert(n, -1) ์ด์œ  : elif i>=10 and code[L] == i//10 and code[L+1] == i%10: ๋ฌธ์žฅ์—์„œ ๋งŒ์•ฝ ๋งˆ์ง€๋ง‰ ์ธ๋ฑ์Šค์˜ ๊ฐ’์ด 1์ด๋‚˜ 2์ธ ๊ฒฝ์šฐ, code[L] == i//10์ด ํ†ต๊ณผ๋˜์–ด code[L+1] == i%10์˜ L+1 ๋ถ€๋ถ„์—์„œ ์ธ๋ฑ์Šค ๋ฒ”์œ„ ์—๋Ÿฌ๊ฐ€ ๋‚  ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์— -1 ์‚ฝ์ž…ํ•ด๋‘๊ธฐ. (1์ด๋‚˜ 2๊ฐ€ ์•„๋‹ˆ๋ผ๋ฉด code[L] == i//10์—์„œ๋ถ€ํ„ฐ ํ†ต๊ณผ๊ฐ€ ๋˜์ง€ ์•Š์Œ. ์•ŒํŒŒ๋ฒณ์€ 26๊นŒ์ง€๋งŒ ์žˆ๊ธฐ ๋•Œ๋ฌธ. 10์˜ ์ž๋ฆฌ๊ฐ€ 2๊ฐ€ ์ตœ๋Œ€)

def DFS(L, P):
    global cnt
    if L == n:
        cnt += 1
        for j in range(P): # P๊ฐ€ ํ•˜๋‚˜ ์ฆ๊ฐ€ํ•ด์„œ ์™”๊ธฐ ๋•Œ๋ฌธ์— 0~P๊นŒ์ง€ ๋Œ๊ฒŒ ๋จ
            print(chr(res[j]+64), end='')
        print()
    else:
        for i in range(1, 27):  # 1~26
            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:  # i๊ฐ€ ๋‘์ž๋ฆฌ ์ˆซ์ž์ผ๋•Œ
                res[P] = i
                DFS(L+2, P+1)

code = list(map(int, input()))  # ์ž…๋ ฅ ๋ฆฌ์ŠคํŠธ๋กœ ๋ฐ›๊ธฐ
n = len(code)
code.insert(n, -1)
res = [0] * (n+3)
cnt = 0
DFS(0, 0)

print(cnt)

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ