파이썬 알고리즘 | 재귀함수와 스택(중요)

완전탐색 (백트랙킹, 상태트리와 CUT EDGE)-DFS(깊이우선탐색)기초

(1) 재귀함수

• 자기 자신을 호출하는 함수를 가리킨다
• 실행될 때 스택이라는 자료구조를 사용한다
• 알고리즘 문제를 풀 때반복문의 역할을 수행해준다
• 큰 작업 하나를 동일하면서 간단한 작업 여러 개로 나눌 수 있을 때 유용

<입력값이 3이라고 할 때>

def DFS(x) :
    if x>0:
    	print(x)
        DFS(x-1)
        
if __name__=='__main__' : 
    n=int(input())
    DFS(n)
    

=> print함수를 밑으로 하면 3, 2, 1 출력

def DFS(x) :
    if x>0:
        DFS(x-1)
        print(x)
       
if __name__=='__main__' : 
    n=int(input())
    DFS(n)
    

=>이렇게 하면 1, 2, 3 이렇게 출력

• 스택이라는 구조를 사용하기 때문
  ==> (밑) DFS(3)-DFS(2)-DFS(1)-DFS(0)에선 X<0이니깐 멈추기 그리고
  DFS(1)-DFS(2)-DFS(3) 순으로 나온다

<형식>

def DFS(x) : 


if __name__=='__main__' : 
    n=int(input())
    DFS(n)

위에 dfs를 정의해주고 밑에서 사용하면 된다
dfs 나중에 출력할 때 프린트를 호출 뒤에 두면 거꾸로 출력되구(나중에 입력한 값부터) , 호출 앞에 넣으면 처음 넣은 값부터 순서대로 나온다