[Python] 백트래킹

백트래킹이란?

• 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하다, 원하는 값과 불일치하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전 단계로 올라가는(방금 왔던 길을 되짚어가는) 알고리즘

 

백트래킹과 DFS의 차이

• 백트래킹
  • 불필요한 탐색을 하지 않는다.
• DFS
  • 모든 경우의 수를 탐색한다.

 

백트래킹 구현

• 완전탐색 기법인 BFS 와 DFS 로 모두 구현 가능
  • 백트래킹의 특성(전 단계로 다시 올라가는) 때문에 DFS의 구현이 더 편하다.

• 한정 조건 이 가장 중요하다.
  • 모든 경우의 수에서 한정 조건 을 만족하는 경우를 탐색

 

대표 문제

15649번: N과 M (1)

문제

자연수 N과 M이 주어질 때, 숫자 1부터 N까지 중복 없는 M개의 요소를 가진 수열을 구하자

💡 고려 사항

• 배열의 길이가 M을 넘지 않아야 한다.
• 배열 내의 중복된 숫자가 없어야 한다.

N, M = map(int, input().split())
ans = []

def back():
    if len(ans) == M: # 배열의 길이를 확인(재귀함수를 마치는 조건)
        print(' '.join(map(str, arr)))
        return 

    for i in range(1, N+1): # 1 ~ N 까지
        if i not in ans: # 중복 확인(백트래킹에서의 한정 조건)
            ans.append(i) # 배열 추가
            back() # 재귀
            ans.pop() # return으로 돌아오면 이게 실행됨. 1, 2, 3 일때 3을 없앰으로 전 단계로 돌아가는 것
    return
        
back()