N과 M (1) - 15649 번

백트래킹 알고리즘의 기본문제이다.

재귀적으로 돌아가는 dfs 이며, 탐색이 끝나면 바로 전 단계로 돌아가는 형식을 취한다.

 

n,m = map(int,input().split())

# 입력값들의 최대값이 8이므로 넉넉히 10칸으로 만들어줌
arr = [0]*10
is_used = [False]*10

# backtracking funtion
def bt(idx):
    if idx == m:
        for i in range(m):
            print(arr[i],end=' ')
        print()
        return
    for i in range(1,n+1):
        if not is_used[i]:
            arr[idx] = i
            is_used[i] = True
            print('다음 bt', idx + 1)
            print(arr)
            print(is_used)
            bt(idx+1)
            print('bt 탈출 후 false', i)
            print(arr)
            print(is_used)
            is_used[i] = False

# 값을 저장할 배열의 첫번째 인덱스 0을 넣어준다.
bt(0)