15649: N과 M (1)

백준문제:N과 M(1)

내풀이 1

N,M = map(int, input().split())
answer_list = []
check_list = [0] * (N+1)

def dfs(n, small_list):
    if n == M:
        answer_list.append(small_list)
        return
    for i in range(1, N+1):
        if check_list[i] == 0:
            check_list[i] = 1
            dfs(n+1, small_list + [i])
            check_list[i] = 0
dfs(0, [])
for i in answer_list:
    print(*i)

내풀이 2

from itertools import permutations
n,m = map(int, input().split())
answer_list = []

for i in range(1,n+1):
    answer_list.append(i)

for i in list(permutations(answer_list,m)):
    for j in i:
        print(j, end=' ')
    print()

permutations 함수를 사용하면 쉽게 풀 수 있지만 백트래킹의 원리를 파악하기 위해선 내풀이1 대로 참고하는 것이 좋다.

가능한 모든 경우를 실행해서 그 결과에서 정답을 찾는 형태가 백트래킹이고
종료와 정답처리 관련한 부분이 제일 위에 있어야한다.

첫번째 변수는 무엇으로 할건지? -> 함수 안에서 변수의 단계가 진행되는 형태로 할 것 -> n 형태로 표현 -> 이 문제에서 n은 선택된 숫자의 개수 (길이)