와 이건 진짜 모르겠다. 재귀함수로 짜보려고 혼자 열심히 짱구 굴려봤지만 결국 다른 풀이들을 참고했다. 재귀함수 스택 쌓아서 구현하는 게 왜 이렇게 어려운지..ㅠ
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))
이런 코드가 좋다. 굳이 주석 달지 않아도 누구라도 보고 이해할 수 있는 코드
'온라인 저지 > BOJ' 카테고리의 다른 글
[BOJ/Java] 2309 일곱 난쟁이 (0) | 2022.01.23 |
---|---|
[BOJ/Python] 16926 배열 돌리기 1 (0) | 2022.01.19 |
[BOJ/Python] 2447 별 찍기 - 10, 11729 하노이 탑 이동 순서 (0) | 2021.10.03 |
[BOJ/C] 15757 큰 수 A+B (0) | 2021.09.27 |
[BOJ/C]1157 단어 공부 (0) | 2021.09.25 |
댓글