Computer ScienceAlgorithmTheory

16. Backtracking

Backtracking

답이 x1, x2, x3… 이런 형식으로 도출되는 문제에서, 유효한 답을 모두 찾는 경우 사용되는 알고리즘 기법

x1부터 차례대로 결정하면서 만약 어느 순간 조건에 맞는 답을 도출 못하는 상황에 마주하면,
그 전 단계로 돌아가 다른 선택지로 다시 답을 찾아가는 방법이다.

이 기법은 굳이 더 알아보지 않아도 되는 경우를 확인하지 않도록 설계하는 것이 가장 중요하다.

psuedo code

1
2
3
4
5
6
7
8
9
def backtrack(k):
    if k > n:
        print(x)
    else:
        for each possible value x of x[k]:
            if B(x[1], ... , x[k]) is valid:
            #B는 x1~xk가 해의 일부가 될 수 있는지를 검증
                x[k] = x
                backtrack(k+1)

이런 방식은 미로 탈출하기 등에 적용할 수 있다.

N queens 문제

n X n 체스판에 n개의 퀸을 배치해야 한다.
다만 각 퀸들의 공격권에 다른 퀸이 있으면 없도록 배치해야 할 때, 배치 가능한 방법 갯수를 구하라.

x라는 배열이 각 퀸의 위치를 인덱스가 행을, 밸류값을 열로 나타낸다.
이제 x[0] = 0은 (0,0)에 퀸이 존재함을 의미한다.

그러면 이제 backtracking을 위해 x[0] = 0 이라고 가정하자.
x[1]는 0과 1이 될 수 없다.(세로줄 겹침, 대각선 겹침.)
x[1] = 2인 경우는 일단 문제는 없으니 x[1] = 2 로 가정하고 넘어간다.

x[2] 는 이제 0, 1, 2, 3 모두 될 수 없다.(두 퀸과 무조건 겹침)
즉 조건을 만족할 수 없으므로, x[1]의 경우로 backtracking한다!

이런 과정을 통해 x[3]이 배치될 때까지 반복하면 backtracking을 통해 답을 찾을 수 있다.

Share