백트래킹 알고리즘의 기본문제이다.
재귀적으로 돌아가는 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)
'백준' 카테고리의 다른 글
유기농 배추 - 1012번 (0) | 2022.10.04 |
---|---|
N과 M (2) - 15650 번 (0) | 2022.10.03 |
ACM 호텔 - 10250 번 (0) | 2022.10.01 |
이항 계수 1 - 11050번 (0) | 2022.10.01 |
분해합 - 2231번 (0) | 2022.09.30 |
댓글