[CS] 백트래킹(Backtracking)

백트래킹(Backtracking)

---

• 모든 가능한 해를 탐색하는 알고리즘 기법으로, 주로 깊이 우선 탐색(DFS)를 기반으로 합니다.

• 가능한 모든 경우를 탐색하면서도 불필요한 경로는 가지치기(Pruning)를 통해 제거하여 효율성을 높입니다

• 자바스크립트에서 백트래킹을 구현할 때는 재귀 함수를 사용하는 것이 일반적입니다. 여기서는 자바스크립트로 백트래킹을 구현하는 방법과 예제를 소개합니다.

백트래킹 알고리즘의 기본 구조

1. 해가 되는지 검사: 현재 상태가 문제의 해인지 검사합니다.
2. 가지치기: 유망하지 않은 노드는 더 이상 탐색하지 않습니다.
3. 재귀 호출: 유망한 노드에 대해 재귀적으로 탐색을 진행합니다.
4. 되돌아가기: 탐색이 끝나면 이전 상태로 되돌아갑니다.

---

자바스크립트 백트래킹 예제: N-Queen 문제

• N-Queen 문제는 N x N 체스판 위에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제입니다. 이 문제는 백트래킹을 통해 해결할 수 있습니다.

function solveNQueens(n) {
    let solutions = [];
    let board = Array(n).fill().map(() => Array(n).fill('.'));

    function isSafe(row, col) {
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q') return false;
            if (col - (row - i) >= 0 && board[i][col - (row - i)] === 'Q') return false;
            if (col + (row - i) < n && board[i][col + (row - i)] === 'Q') return false;
        }
        return true;
    }

    function backtrack(row) {
        if (row === n) {
            solutions.push(board.map(r => r.join('')));
            return;
        }

        for (let col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                board[row][col] = 'Q';
                backtrack(row + 1);
                board[row][col] = '.';
            }
        }
    }

    backtrack(0);
    return solutions;
}

console.log(solveNQueens(4));

Code

• isSafe 함수: 현재 퀸을 놓으려는 위치가 안전한지를 검사합니다. 같은 열, 대각선에 다른 퀸이 있는지를 확인합니다.

• backtrack 함수: 재귀적으로 각 행에 퀸을 배치하고, 가능한 모든 배치를 탐색합니다. 퀸을 놓은 후에는 다음 행으로 이동하며, 조건에 맞지 않으면 이전 상태로 돌아갑니다.

• 해 찾기: 모든 퀸이 배치되면 현재 보드 상태를 해로 저장합니다.

주의사항

1. 가지치기: 불필요한 경로를 미리 차단하여 탐색 공간을 줄이는 데 필수적입니다. 유망하지 않은 경로는 빨리 포기하여 시간과 자원을 절약해야 합니다
2. 재귀 깊이 관리: 재귀 호출이 깊어질 수 있으므로, 자바스크립트의 최대 호출 스택 크기를 초과하지 않도록 주의해야 합니다. 재귀 깊이를 제한하거나 필요한 경우 반복문을 사용하여 대체할 수 있습니다.
3. 상태 복원: 각 단계에서 선택한 상태를 정확하게 복원해야 합니다. 선택을 취소하고 이전 상태로 돌아가는 과정이 올바르게 구현되어야 다음 탐색에 영향을 주지 않습니다
4. 종료 조건 설정: 종료 조건을 명확히 설정해야 합니다. 모든 가능한 해를 찾거나 특정 조건을 만족하는 해를 찾으면 탐색을 중단할 수 있도록 해야 합니다
5. 메모리 사용 최적화: 백트래킹은 모든 가능한 경로를 탐색하기 때문에 메모리 사용량이 많아질 수 있습니다. 필요한 데이터만 유지하고 나머지는 적절히 해제하여 메모리 사용을 최적화해야 합니다.
6. 효율적인 데이터 구조 사용: 문제에 따라 적절한 데이터 구조를 선택하여 효율성을 높일 수 있습니다. 예를 들어, 집합(Set)이나 맵(Map)을 사용하여 중복을 피하거나 빠른 조회가 가능하도록 할 수 있습니다