[BOJ/Python] 15649 N과 M(1)

와 이건 진짜 모르겠다. 재귀함수로 짜보려고 혼자 열심히 짱구 굴려봤지만 결국 다른 풀이들을 참고했다. 재귀함수 스택 쌓아서 구현하는 게 왜 이렇게 어려운지..ㅠ

import sys, itertools
n, m = map(int,sys.stdin.readline().split())
list_for_print=[]#전역변수 리스트 선언

def bt():
    if len(list_for_print) == m:#list 길이랑 m이랑 같으면 출력
        print(' '.join(map(str, list_for_print)))
    
    for i in range(1, n+1):#1부터 n까지
        if i in list_for_print:#해당 숫자i가 list 안에 있으면 뒤에 수행 안하고 다시 for문 복귀
            continue
        list_for_print.append(i)#if문 통과했으면 해당 i는 list에 추가
        bt()#다시 함수 수행(list는 어차피 전역으로 되어 있다.)
        list_for_print.pop()#for문 안에 있는 bt 다 돌아서 출력했으면 다시 다 빼줘야함

bt()

뭔가 경우의 수가 많아지면 좀 머리가 하얘지는 것 같다.

n, m = map(int, input().split())
visited=[False]*n #탐사 여부 check
out=[]# 출력하기위한 리스트
def bt(depth, n, m):
    if depth == m:#탈출조건(recursion은 항상 탈출조건이 있어야 한다.)
        print(' '.join(map(str, out)))#list 내용들을 묶어서 출력
        return
    for i in range(len(visited)):#visited를 한바퀴 돌면서
        if not visited[i]:#visit되지 않았으면 이하 실행
            visited[i]=True#visit 시작
            out.append(i+1)#dfs는 stack을 이용하므로 집어넣기 어차피 이 stack list는 전역으로 언되어 있다.
            bt(depth+1,n,m)
            visited[i]=False#수행해줬으니 원상복귀 시키고
            out.pop() #넣어서 수행했으니 stack도 원상복귀
bt(0,n,m)#depth = 0 부터 백트래킹 시작

 

itertools 배우고서 안써먹었다 또..

결국 문제에서 요구하는 것은 permutation이니까 permutations 함수 써도 된다.

#이하 permutations 이용
from itertools import permutations
import sys
n,m=map(int,sys.stdin.readline().split())
list_of_n = [str(i) for i in range(1,n+1)]
for num in list(permutations(list_of_n,m)):
    print(" ".join(num))

이런 코드가 좋다. 굳이 주석 달지 않아도 누구라도 보고 이해할 수 있는 코드