[백준] 15651 파이썬(python) : N과 M (3)

15651번 : N과 M (3)

 

 

import sys
n ,m = map(int, sys.stdin.readline().split())
arr = [] #1
def backTracking(depth): #2
    if depth == m: #3
        print(*arr) #4
        return
    for i in range(1, n+1):
        arr.append(i) #5
        backTracking(depth+1) #6
        arr.pop() #7
backTracking(0)

 

#1 : 재귀를 사용해서 원소를 넣었다 뺏다 사용할 스택

#2 : 재귀를 이용한 백트래킹 함수 depth는 스택의 길이를 의미

#3 : depth == m은 스택의 길이가 입력값 m과 같아지면 출력

#4 : 리스트 언패킹을 이용하였다

#5 : 반복문을 이용해서 answer리스트에 원소 삽입 depth가 0일때 모든 첫번째 원소를 1~n까지 한번씩 넣어줌

#6 : #5에서 원소를 넣고 재귀호출 #7과 반복문을 이용해서 각 위치에 1~n까지 원소 한번씩 모두 넣을 수 있고 스택의 길이가 입력값 m과 같아지면 #4에서 리스트 출력

#7 : 출력이 끝난 마지막 위치의 원소 꺼냄 #7이 끝나면 반복문으로 다음 원소를 추가(#5) 그리고 재귀호출로 출력을 반복 원소가 입력값 n과 같아질때까지

 

*재귀를 이용하는 문제는 언제나 어렵다. 천천히 과정을 종이에 써내려다보면 이해가 되지만 이렇게 간결한 코드를 작성한 사람들이 굉장히 대단하다고 느껴진다. 열심히 복습해야겠다는 생각뿐이다.

 

백트래킹은 dfs에서 가지치기를 하여 실행 횟수를 줄여주는 것이다. 여기서 for문이 가지치기에 해당한다.