백준 15649: N과M(1)

◎백트래킹 문제 

◎재귀를 이용하여 문제 풀음

def dfs(cnt): #cnt가 M이 되면 arr출력하는 함수 만들기
    #조건 생성 : cnt가 M과 같아질 때 arr출력
    if cnt == M:
        for i in range(len(arr)):
            print(arr[i], end=' ')
        return
    #visit 추적
    for i in range(N):
        #visit이 True일 경우에는 건너뛰고 계속 진행한다
        if visit[i]:
            continue
        #방문한 곳은 True로 변경
        visit[i] = True
        #i번째 idx arr에 append해줌
        arr.append(lst[i])
        #재귀(stack형식으로 쌓인다는 점 기억)
        #큰 깨달음 : 함수 자체가 stack에 쌓임 
        dfs(cnt+1)
        arr.pop()
        print(arr)
        print(visit)
        visit[i] = False

import sys
sys.stdin = open('15649.txt')

#N, M 입력받기
N, M = map(int, input().split())
#list생성
lst = [i+1 for i in range(N)]
#방문한곳 체크
visit = [False]*N
#값넣을 곳 생성
arr = []
#arr출력할 함수실행
dfs(0)