[백 트래킹 기법 이해 (BackTracking)]
- 백트래킹 혹은 퇴각 검색으로 부르며, 제약 조건 만족 문제에서 해를 찾기 위한 전략이다.
* 제약조건 만족 : 해를 찾기 위해 후보군에 제약 조건을 점진적 체크, 해당 후보군이 제약 조건을 만족할 수
없다고 판단되면 즉시 backtrack으로 넘어가서 이 후보군을 탐색 후보군에서 완전 제외 시킴*
즉 가능성이 없는 후보군을 삭제한 후, 해당 후보군을 다시는 체크하지 않으며, 이를 통해 최적의 해를 찾는 방법이다.
행렬에서 각 행이 0,1,2,3... 과 같이 점진적 증가인 경우를 카운트해서 반환한다면,
그 행의 맨 뒤까지 탐색할 때 점진적인 증가가 발생되지 않은 시점에서 해당 후보군을 제외시키고,
다른 탐색 후보군을 탐색하는 방법 또 퇴각 검색 기법 중 하나이다.
-> 실제 구현시, 고려할 수 있는 모든 경우의 수(후보군)를 상태 공간 트리를 통해서 표현한다.
각 후보군은 DFS 방식으로 확인하며, 제약에 맞지 않는 조건 발견 시 해의 후보가 될만한 곳으로 넘어가서 탐색한다.
Promising: 해당 루트가 조건에 맞는지를 검사하는 기법
Pruning : 가지치기라는 뜻으로 조건에 맞지 않으면 포기하고 다른 루트로 돌아서는 기법 (시간 절약)
-> 백 트래킹 기법은 각 루트에 대하여 Promising을 진행하고, 조건에 맞지 않는다면 Pruning을 진행한다.
[상태 공간 트리 (State Space Tree)]
- 문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리이다.
-> 상태 공간 트리에서 점진적 탐색을 진행하고, 조건에 맞지 않는 노드는 가지치기를 진행한다.
[N Queen 문제 (백 트래킹의 기초)]
대표적인 백 트래킹 문제로 N * N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제이다.
퀸은 아래의 그림과 같이 이동할 수 있으며, 배치된 퀸이 공격할 수 없도록 다른 퀸을 배치해야 한다.
-> 백 트래킹 방식으로 문제를 해결하나 실제로 트리를 그리지 않고 N*N의 배열을 만든 후 탐색을 한다.
-> Promising for N Queen 기법을 사용한다.
[Promising for N Queen 문제!]
해당 루트가 조건에 맞는지를 검사하는 기법을 활용
현재까지 앞선 행에서 배치한 퀸이 이동할 수 없는 위치가 있는지를 확인한다.
한 행에는 하나의 퀸만 배치 가능하므로 수평 체크를 제외한 수직, 대각선 체크를 한다.
수직과 대각선 체크를 통해서 조건에 만족하지 않는 퀸을 발견할 경우
False를 return 하면서 백 트래킹 기법을 사용하는 것이다.
수직 체크인 경우 : 현재 col (열)과 다른 퀸의 col이 같은 경우 (False를 반환)
대각선 체크인 경우 : 현재 col(열)과 다른 퀸의 col의 차이의 절댓값이
현재 row(행)과 다른 퀸의 row의 절댓값과 같은 경우 (False를 반환)
수평인 경우를 제외하고 두 가지 경우 중 하나를 만족한다면 퀸의 규칙을 위배한다.
이때 백트래킹 기법으로 다른 탐색을 진행한다.
[Python 코드로 확인하기]
우선 각 변수들을 확인해보면,
1. N : N*N의 행렬의 격자판의 크기
2. current_row : 현재 탐색 중인 행
3. current_candidate : 기존 퀸의 배치 정보
4. final_result : 최종 결괏값
이며, 실행 함수인 solve_n_queens(N)을 선언한다.
def solve_n_queens(N):
final_result =[]
DFS(N,0,[],final_result)
return final_result
다음으로는 깊이 우선 탐색인 DFS 함수를 선언한다.
def DFS(N,current_row,current_candidate,final_result):
if current_row ==N:#마지막 행
final_result.append(current_candidate[:]) #얇은 복사
return
for candidate_col in range(N):
if is_available(current_candidate,candidate_col):
current_candidate.append(candidate_col)
DFS(N, current_row+1,current_candidate,final_result)
current_candidate.pop() #다른 부분으로 이동
우선 만약 현재 행이 마지막 행일 경우 기존 퀸의 배치 정보를 결과에 추가하고 return 한다.
for문을 돌면서 is_available 함수를 실행한다.
그 결과에 따라서 기존 퀸의 배치 정보에 새로운 열을 추가하고, DFS 함수를 새로 호출한다.
is_abailable 함수는 아래와 같다.
def is_available(candidate, current_col):
current_row = len(candidate) # 현재 행은 퀸의 개수 (한 행에 하나의 퀸이 있기 때문)
for queen_row in range(current_row):
if candidate[queen_row] == current_col:
# 같은 열에 있는 경우
return False
if abs(candidate[queen_row] - current_col) == current_row - queen_row:
# 대각선에 있는 경우
return False
return True # 조건에 만족 (해당 위치에 퀸 넣기)
위에서 설정한 조건을 탐색하는 함수이며, 현재 행 (=퀸의 개수 여태 추가한 퀸의 수는 행의 값이 됨)을
기준으로 수직 탐색과 대각선 탐색을 진행한다.
조건에 걸리는 경우 False를 반환, 모든 조건을 만족한 경우 True를 반환한다.
is_abailable의 결과에 따라서 해당 값이 참이면 퀸의 위치를 추가하고, 탐색을 진행한다.
해당 결과가 거짓이면 해당 행에는 퀸의 위치가 없으므로 다른 조건으로 이동한다.
결과적으로 current_row가 최종 행에 도달할 경우 더 이상 퀸이 없으므로 final_result에
현재까지의 퀸의 위치를 추가하고 반환한다.
최종 반환 값은 위와 같으며, 퀸이 존재하는 위치를 나타내고 있다.
퀸의 존재하는 경우는 위와 같으며,
[1,3,0,2]인 경우 4*4의 격자에서 0번 행의 1열, 1번 행의 3열, 2번 행의 0열, 3번 행의 2열에 퀸이 존재하고,
[2,0,3,1]인 경우 4*4의 격자에서 0번 행의 2열, 1번 행의 0열, 2번 행의 3열, 3번 행의 1열에 퀸이 존재한다.
즉 4*4인 격자인 경우 퀸이 최대로 존재할 수 있는 경우의 수는 2가지이며 각 경우의 수별로 3개의 퀸을 놀 수 있다.
[리뷰]
문제풀이 시간을 절약할 수 있는 매우 유용한 방법이다.
여러번 반복해서 공부하고, 숙지한다면 큰 도움이 될 것 같다.