[알고리즘 기법] 백트랙킹(Back-Tracking)

1. 백트래킹이란?

백트래킹(Back-Tracking)은 모든 경우의 수를 탐색하는 브루트포스(Brute Force)와 유사하지만, 탐색 과정에서 '답이 될 가능성'을 실시간으로 판단한다는 점에서 차이가 있습니다.

• 순차적 생성: 답을 한 번에 완성하는 것이 아니라, 여러 단계(Step)에 걸쳐 순차적으로 답을 만들어 나갑니다.
• 가지치기(Pruning): 현재 단계에서 다음 단계로 넘어갈 때, 해당 경로가 답으로 갈 수 없다고 판단되면 더 이상 탐색하지 않고 즉시 뒤로 돌아갑니다.
• 효율성: 가지치기를 통해 오답 경로에 소모되는 리소스 낭비를 획기적으로 줄일 수 있습니다.

2. 구현 방식

백트래킹은 주로 DFS 형식을 빌려 재귀적으로 구현합니다. 유효한 상태를 찾아 깊게 탐색하다가, 막다른 길에 다다르면 이전 상태로 복귀(Back)하는 것이 핵심입니다.

3. 코드 (N-Queens 예시)

가장 대표적인 백트래킹 문제인 N-Queens를 통해 실제 구현 모습을 살펴보겠습니다.

https://pirograming.tistory.com/76

[LeetCode] 51 N-Queens(Java)

class Solution {
    List<List<String>> ret;
    public List<List<String>> solveNQueens(int n) {
        ret = new ArrayList<>();
        List<List<Integer>> queens = new ArrayList<>();
        recall(n, queens, 0);

        return ret;
    }

    private void recall(int n, List<List<Integer>> queens, int row) {
        // 1. 기저 조건: 모든 행에 퀸을 다 배치했을 때
        if (row >= n && queens.size() == n) {
            List<String> sl = getStrings(n, queens);
            ret.add(sl);
            return;
        }
        
        // 2. 현재 행(row)에서 각 열(col)에 퀸을 놓아보기
        for (int col = 0; col < n; col++) {
            if (isPosable(queens, row, col)) {
                queens.add(List.of(row, col)); // 퀸 배치
                recall(n, queens, row + 1);    // 다음 행으로 이동
                queens.removeLast();           // 백트래킹 (원태 복귀)
            }
        }
    }

    // 퀸의 위치 리스트를 문제에서 요구하는 문자열 리스트 포맷으로 변환
    private static List<String> getStrings(int n, List<List<Integer>> queens) {
        List<String> sl = new ArrayList<>();
        for (int row = 0; row < queens.size(); row++) {
            List<Integer> queen = queens.get(row);
            StringBuilder sb = new StringBuilder();
            for (int col = 0; col < n; col++) {
                if (queen.get(0) == row && queen.get(1) == col) {
                    sb.append('Q');
                } else {
                    sb.append('.');
                }
            }
            sl.add(sb.toString());
        }
        return sl;
    }

    // 현재 위치 (row, col)에 퀸을 놓을 수 있는지 체크
    private boolean isPosable(List<List<Integer>> queens, int row, int col) {
        for (List<Integer> queen : queens) {
            if (queen.get(1) == col || // 같은 열 체크
                    queen.get(0) + queen.get(1) == row + col || // 대각선 / 체크
                    queen.get(0) - queen.get(1) == row - col)   // 대각선 \ 체크
                return false;
        }
        return true;
    }
}

4. 코드 포인트 해설

• recall 메서드: 재귀적으로 호출되며 답을 찾아 나가는 핵심 엔진입니다.
• 기저 조건(Base Case): 모든 행(row)에 퀸 배치를 완료하여 queens.size() == n이 되면, 유효한 정답을 하나 찾은 것으로 간주하고 결과 리스트에 저장합니다.
• 의사 결정과 복구: queens.add()를 통해 퀸을 배치해보고, 다음 행으로 넘어갔다가 돌아온 후에는 queens.removeLast()를 호출합니다. 이는 이전의 선택을 취소하고 '깨끗한 상태'에서 다음 열을 시도하기 위함입니다.
• 탐색의 흐름: 한 행에서 어떤 열에도 퀸을 놓을 수 없는 상황이 오면 재귀가 자연스럽게 종료되며 이전 행으로 돌아갑니다. 이것이 바로 백트래킹의 자동 가지치기 메커니즘입니다.

5. 마치며

백트래킹은 "가능성이 있는 길만 가고, 아니면 빨리 돌아온다"는 전략을 코드로 구현한 것입니다. 재귀 호출 직후에 상태를 원래대로 돌려놓는 과정만 잘 이해한다면, 복잡한 완전 탐색 문제도 효율적으로 해결할 수 있습니다.