백준 10597 - 순열 장난 Python

import sys
from collections import deque
def func(k):
    if k == len(N):
        max_num = 0
        for i in range(len(arr)):
            max_num = max(max_num,int(arr[i]))
        
        if max_num == len(arr):
            for i in range(len(arr)):
                print(int(arr[i]), end = ' ')
            sys.exit()            
        return
    if k < len(N) and int(N[k]) <= 50 and not visit[int(N[k])]:
        visit[int(N[k])] = 1
        arr.append(N[k])
        func(k+1)
        arr.pop()
        visit[int(N[k])] = 0
    if k + 1 < len(N) and int(N[k:k+2]) <= 50 and not visit[int(N[k:k+2])]:
        visit[int(N[k:k+2])] = 1
        arr.append(N[k:k+2])
        func(k+2)
        visit[int(N[k:k+2])] = 0
        arr.pop()
    
arr = deque()
N = input()
visit = [0] * 51
func(0)

 

중간의 두 개의 if문이 백트래킹입니다.

숫자가 최대 50개이므로, 한 개 혹은 두 개씩 숫자를 잘라서 확인해야 합니다.

재귀를 호출하고 나서는 꼭 재귀를 호출하기 전 상태로 돌아가는 것이 백트래킹의 핵심입니다.

visit[] = 0으로 만들거나, pop()을 해 주는 이유입니다.

 

제일 먼저 나오는 if는 N의 끝까지 읽었을 때,

배열에서 가장 큰 값과 배열의 길이가 같다면 수열이 완성됐다고 판단하고 종료합니다.