역추적(Backtracking)은 문제 해결을 위한 알고리즘 기반 기법으로, 재귀 호출(recursive call)을 활용하여 해답을 한 단계씩 구축해 나가는 방식입니다. 이 기법은 문제에 주어진 제약 조건을 바탕으로, 최종 해답으로 이어지지 않는 후보 해답들을 탐색 과정 중간에 제거함으로써 탐색 공간을 효율적으로 줄여 나갑니다.
역추적 알고리즘은 다음과 같은 특정 유형의 문제에 주로 적용됩니다.
결정 문제(Decision Problem): 문제의 실현 가능한(feasible) 해답을 찾는 데 사용됩니다.
최적화 문제(Optimisation Problem): 적용 가능한 해답들 중 가장 최선의 해를 찾는 데 사용됩니다.
열거 문제(Enumeration Problem): 문제의 모든 실현 가능한 해답들의 집합을 찾는 데 사용됩니다.
역추적 문제에서 알고리즘은 해답에 도달하는 일련의 경로를 탐색합니다. 이 경로에는 여러 개의 작은 체크포인트가 존재하며, 특정 지점에서 실현 가능한 해답을 찾지 못하면 해당 체크포인트로 되돌아가 다른 경로를 시도할 수 있습니다.
다음 예시를 통해 살펴보겠습니다.
위 그림에서 각 색상은 다음을 의미합니다.
초록색(Green): 시작점
파란색(Blue): 중간 지점
빨간색(Red): 실현 가능한 해답이 없는 지점
진한 초록색(Dark Green): 최종 해답 지점
알고리즘이 경로의 끝까지 전파되면 해당 지점이 해답인지 확인합니다. 해답이라면 결과를 반환하고, 그렇지 않다면 한 단계 뒤의 지점으로 역추적하여 다음 후보 지점을 탐색하며 해답을 찾습니다.
알고리즘
1단계 − 현재 위치(current_position)가 목표 지점이면 성공(success)을 반환한다. 2단계 − 그렇지 않으면, 3단계 − 현재 위치가 끝점(end point)이면 실패(failed)를 반환한다. 4단계 − 현재 위치가 끝점이 아니라면 탐색을 계속하고 위 단계를 반복한다.
이제 이 역추적 기법을 활용하여 N-퀸 문제(N-Queen Problem)의 해답을 찾아보겠습니다.
N-퀸 문제에서는 NxN 크기의 체스판이 주어지며, 어떤 두 퀸도 서로 공격하지 않도록 n개의 퀸을 배치해야 합니다. 퀸은 자신의 가로, 세로, 대각선 방향에 있는 다른 퀸을 공격할 수 있습니다. 여기서는 4-퀸 문제를 다뤄보겠습니다.
해답은 다음과 같습니다.
위 출력은 퀸이 배치된 위치를 1로 표시한 이진 행렬입니다.
{0 , 1 , 0 , 0}
{0 , 0 , 0 , 1}
{1 , 0 , 0 , 0}
{0 , 0 , 1 , 0}
N-퀸 문제를 해결하기 위해서는 한 행(row)의 서로 다른 위치에 퀸을 놓아보면서, 다른 퀸과 충돌하는지 검사합니다. 현재 배치 상태에서 두 퀸이 서로 공격하고 있다면, 이전 위치로 역추적하여 퀸의 위치를 변경한 뒤 다시 충돌 여부를 확인합니다.
알고리즘
1단계 − 배열의 첫 번째 위치부터 시작한다.
2단계 − 체스판에 퀸을 배치하고 검사한다. 다음을 수행한다.
2.1단계 − 퀸을 배치한 후 해당 위치를 해답의 일부로 표시하고, 이 배치가 해답으로 이어지는지 재귀적으로 검사한다.
2.2단계 − 퀸을 배치했는데 해답으로 이어지지 않는다면 역추적하여 이전 단계로 돌아가 다른 행에 퀸을 배치한다.
2.3단계 − 퀸 배치가 해답으로 이어지면 TRUE를 반환한다.
3단계 − 모든 퀸이 배치되었다면 TRUE를 반환한다.
4단계 − 모든 행을 시도했는데도 해답을 찾지 못했다면 FALSE를 반환한다.
이번에는 역추적을 활용하여 미로 속 쥐(Rat in a Maze) 문제를 해결해 보겠습니다.
미로 속 쥐 문제에서는 NxN 크기의 미로가 주어지며, 쥐는 미로의 시작 위치인 [0][0]에서 출발하여 배열의 마지막 위치인 [n-1][n-1]에 도달해야 합니다. 이 경로에는 해답으로 이어지지 않는 막다른 길(dead end)들이 존재합니다.
이 문제에 역추적을 적용하면, 쥐는 한 걸음씩 이동하면서 최종 목표 위치에 도달할 때까지 탐색을 진행합니다. 막다른 길에 부딪히면 이전 분기점으로 되돌아가 다른 경로를 시도하는 방식입니다.
아래 2차원 배열은 이 문제의 예시를 보여줍니다.
여기서 점선은 이동한 경로를 나타냅니다.