해결책에 대한 후보를 구축하다 가능성이 없다고 판단되는 즉시 후보를 포기(백트랙 Backtrack)해 정답을 찾아가는 범용적인 알고리즘
DFS와 짝꿍처럼 등장하지만 백트래킹은 DFS보다 더 광의의 의미를 지닌다
백준 N과 M (1)
https://www.acmicpc.net/problem/15649
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력
def permutation(n, lst):
# 종료 조건 + 정답 처리
if n == M:
result.append(lst)
return
# 하부 함수 호출
for i in range(1, N+1):
if visited[i] == 0: # 선택 안한 경우
visited[i] = 1
permutation(n + 1, lst+[i])
visited[i] = 0
# (1 ≤ M ≤ N ≤ 8)
N, M = map(int, (input().split()))
result = [] # 정답 저장용
visited = [0] * (N + 1) # 중복 확인용
permutation(0, [])
for lst in result:
print(*lst)
백트래킹 조건에 의해 아직 방문하지 않은 경우에만 방문하여 수열을 구한다!