[ 알고리즘 ] 백트래킹

1. 개념

해를 찾다가 해가 아니어서 막히면, 되돌아가면 다시 해를 탐색하는 방법.

DFS의 일종.

모든 경우의 수 중에서 특정 조건을 만족하는 경우만 살펴보는 방법. 가지치기.

--> 최적화 문제와 결정 문제일 때

 

2. 방법

DFS 등으로 모든 경우의 수를 탐색할 때, 조건으로 절대 해가 아닌 경우일 때는 탐색을 중단하고 그 이전으로 돌아가, 즉 '백트래킹'해서 다른 경우를 탐색하는 방법으로 주로 구현.

주로 재귀로 구현하다가 조건이 맞지 않으면 종료.

 

3. 예제

https://www.acmicpc.net/problem/15651

n, m = map(int,input().split())
l = []

def dfs(num):
    if len(l) == m:
        for i in l:
            print(i, end = ' ')
        print()
        return
    for i in range(1, n+1):
        l.append(i)
        dfs(i)
        l.pop()

dfs(1)

 

4. DFS와 비교

DFS는 가능한 모든 경로를 탐색. 경우의 수 줄일 수 없다.

--> N! 가지의 경우의 수를 가진 문제 처리 불가

 

백트래킹은 지금의 경로가 해가 아닐 것 같으면 그 경로를 더 이상 가지 않고 되돌아간다. 경우의 수 줄일 수 있다.

--> 가지치기 : 불필요한 부분 쳐내고, 최대한 올바른 쪽으로 간다.

--> N! 가지의 경우의 수를 가진 문제일 때, 불필요한 경로를 미리 잘 차단한다면 풀 수 있지만, 최악의 경우에는 불가능.

 

 

 

참고블로그 : https://chanhuiseok.github.io/posts/algo-23/