[알고리즘] 백트래킹

백트래킹

• 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법
• DFS와 다른점
  • DFS는 가능한 모든 경로를 탐색
  • 백트래킹은 해를 찾는 도중 해가 될 수 없다고 판단되면, 되돌아가서 다시 해를 찾음 → 재귀 함수를 마치는 조건이 존재!
• 재귀적으로 구현 (스택으로도 가능)
• 재귀 함수가 종료되는 시점 명시 필요

시간 복잡도

• 문제의 조건에 따라 다름
• 중복이 가능 : O(N^N) (보통 N=8까지 가능)
• 중복이 불가 : O(N!) (보통 N=10까지 가능)

자료 구조

• 선택한 값 입력 배열
• 방문 여부 확인 (재방문 금지)

예시 코드

• 자연수 N과 M이 주어질 때, 숫자 1부터 N까지 중복 없이 M개를 고른 수열을 모두 구하는 프로그램

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

def backtracking():
	if len(ans) == M:
        print(' '.join(map(str, arr)))
        return 

    for i in range(1, N+1):
        if i not in ans: 
            ans.append(i)
            back()
            ans.pop()
    return
        
backtracking()