[백준 2529 Python 파이썬] 두동전

 

1. dfs, bfs, while, 재귀... 흐름의 기준을 무엇으로 잡느냐가 중요하다.

시간이 흐름의 기준인지... 큐/스택의 개수가 흐름의 기준인지 등

 

2. while이 간단해서 좋지만 재귀를 사용하는 것이 더 낫다.

while로 했다가 재귀로 바꿔야할 경우 멘붕당한다.

나중에 while문 안에서 break 걸면 while 완전종료되고, 넣었다 뺐다 할때 원상복귀시키는 것도 힘들다.

for문 안에 dfs,bfs 등 재귀를 넣고... 그 재귀함수 초반에 종료조건을 넣어주면 불필요한 for문 시, 함수타지 않는다.

 

#처음코드
from collections import deque
import sys

sign_cnt = sys.stdin.readline();
sign_cnt = int(sign_cnt)
sign = sys.stdin.readline().split()
number = list(range(10))
number.reverse()

que = deque()
dap = []
dfs_run_flag = True
i = 0
def dfs(que_cnt) :
    
    global dfs_run_flag
    
    if(not dfs_run_flag) :
        return
        
    for i in range(len(dap)-1) :
        if(sign[i]=='>') :
            if not(dap[i]>dap[i+1]):
                return
        else :
            if not(dap[i]<dap[i+1]):
                return
    if(len(used_number)==(que_cnt)) :
        dfs_run_flag=False
        for i in range(len(dap)) :
        	print(dap[i], end='')
        print()
            
        
    for i in range(len(used_number)) :
        if(used_number_check[i]==False) :
            dap.append(used_number[i])
            used_number_check[i] = True
            que_cnt = que_cnt+1
            dfs(que_cnt)
            dap.pop()
            used_number_check[i] = False
            que_cnt = que_cnt-1



used_number = number[:sign_cnt+1]
used_number_check = [False]*len(used_number)
dfs(0)
used_number = number[-(sign_cnt+1):]
used_number_check = [False]*len(used_number)
used_number.reverse()
que = deque()
dap = []
dfs_run_flag = True
i = 0
dfs(0)

#나중코드
k = int(input())
sign = input().split()
       
def dfs(number, number_used, dap_b, cnt, stop_yn) :
    
    if( stop_yn ) :
        return True
    elif( len(dap_b)==k+1 ) :
        for i in dap_b :
            print(i, end='')
        return True
    else :
        for i in range(len(number)) :
            if(stop_yn) :
                return True
            elif( number_used[i]== True ) :
                continue
            else :
                if ( sign[ cnt ]=='>' ) :
                    if(dap_b[-1]>number[i]) :
                        dap_b.append(number[i])
                        cnt = cnt+1
                        number_used[i]= True
                        stop_yn = dfs(number, number_used, dap_b, cnt, stop_yn)
                        dap_b.pop()
                        cnt = cnt-1
                        number_used[i]= False
                else :
                    if(dap_b[-1]<number[i]) :
                        dap_b.append(number[i])
                        cnt = cnt+1
                        number_used[i]= True
                        stop_yn = dfs(number, number_used, dap_b, cnt, stop_yn)
                        dap_b.pop()
                        cnt = cnt-1
                        number_used[i]= False
        if(stop_yn) :
            return stop_yn
            
def solution (number, number_used, dap_b) :
    
    
    stop_yn = False
    for i in range(len(number)) :
        if(stop_yn) :
            break
        dap_b=[]
        dap_b.append( number[i] )
        number_used[i] = True

        cnt = 0
        stop_yn = dfs(number, number_used, dap_b, cnt, stop_yn)
        number_used[i] = False
        
solution( list(range(9,(9-k)-1,-1)), [False]*(k+1), [])
print()
solution( list(range(0,k+1,1)), [False]*(k+1), [] )​