[백준][Python] 10597 순열장난 : 분기가 있는 DFS

 Tree 탐색등등 종종 나오는 경우의수를 따지는 DFS문제이다. idx 값을 1개 늘리냐 2개 늘리냐의 분기로 재귀를 실시.

실질적인 4방탐색이나 숨바꼭질 같은 문제와 다를게 없다. 재귀로 값을 누적시키며 달릴것이냐 큐나 스택을 이용할 것이냐의 차이. 선택의 문제. 경우의 수. 종료조건은 max값이 수열 길이와 같은 것.

왜 못풀었을까 생각해보자.

import sys
from collections import deque


def DFS(idx):
    # idx 1부터 시작 kriii의 검사가 모두 끝나면 수열의 가장 큰 값을 찾는다.
    if idx == len(kriii):
        high = 0
        for i in range(len(sequence)):
            high = max(high,int(sequence[i]))
        # 가장 큰 값이 수열의 길이와 같으면 출력, 아니면 회귀
        if high == len(sequence):
            print(*list(map(int,(sequence))))
            sys.exit()            
        return
    # dfs로 배열에 하나넣거나 두개는경우를 동시에 둘 다 조사하며 재귀 진행.(분기가 있는 DFS)
    # 글자 하나만 조사.idx 하나 건너뛴다.
    if idx < len(kriii) and int(kriii[idx]) <= 50 and not visited[int(kriii[idx])]:
        visited[int(kriii[idx])] = 1
        sequence.append(kriii[idx])
        DFS(idx+1)
        sequence.pop()
        visited[int(kriii[idx])] = 0

    # 글자 두개조사. 두개짤랐을때 50이하. 그리고 그 숫자가 전에 방문한적 없었을때 방문.idx 2개 건너뛴다.
    if idx + 1 < len(kriii) and int(kriii[idx:idx+2]) <= 50 and not visited[int(kriii[idx:idx+2])]:
        visited[int(kriii[idx:idx+2])] = 1
        sequence.append(kriii[idx:idx+2])
        DFS(idx+2)
        visited[int(kriii[idx:idx+2])] = 0
        sequence.pop()
    

kriii = input()
sequence = deque()
visited = [0] * 51
DFS(0)