백트래킹 (Backtracking)

백트래킹 (Backtracking) 설명:

백트래킹은 결정 문제(decision problem) 해결을 위해 모든 가능한 조합을 시스템적으로 탐색하는 알고리즘 방법론입니다. 백트래킹은 상태 공간 트리(state space tree)의 모든 경로를 추적하여 해를 찾습니다. 만약 현재 경로가 해결책으로 이어질 것 같지 않으면 (즉, 이것이 유망하지(promising) 않으면), 그 경로의 더 깊은 부분으로의 탐색을 포기하고(백트랙) 다른 경로를 선택합니다.

백트래킹의 특징:

1. 유망성 검사: 현재의 경로가 유망한지 검사하는 단계를 포함하며, 유망하지 않은 경로는 더 이상 탐색하지 않습니다.
2. 깊이 우선 탐색 (DFS): 백트래킹은 주로 깊이 우선 탐색 방식으로 가능한 조합을 탐색합니다.
3. 가지치기 (Pruning): 유망하지 않은 경로는 탐색에서 제외시키는 과정을 의미합니다. 이를 통해 불필요한 탐색을 줄여 시간을 절약합니다.

백트래킹의 대표적인 예제:

1. N-Queens 문제: N x N 체스판에 N개의 퀸을 서로 공격할 수 없게 배치하는 문제.
2. 순열 생성: 주어진 집합의 모든 순열을 생성하는 문제.
3. 미로 찾기: 주어진 미로에서 출발점에서 목적지까지의 경로를 찾는 문제.
4. 색칠하기 문제: 주어진 그래프의 최소 색깔로 모든 노드를 색칠하는 문제, 인접한 노드끼리는 다른 색이 되도록.
5. 배낭 문제 (0/1 Knapsack): 주어진 무게와 가치를 가진 아이템들 중에서 제한된 무게 안에서 최대 가치를 얻을 수 있는 아이템의 조합을 찾는 문제.

예제와 솔루션 (N-Queens 문제):

문제:
N x N 체스판에 N개의 퀸을 서로 공격할 수 없게 배치하는 모든 가능한 방법을 찾아라.

function solveNQueens(n) {
    const board = Array.from({ length: n }, () => Array(n).fill('.'));
    const results = [];

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

    const backtrack = (row) => {
        if (row === n) {
            results.push(board.map(row => row.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 results;
}

console.log(solveNQueens(4));

위 코드는 N-Queens 문제를 해결하기 위한 백트래킹 알고리즘을 사용합니다. backtrack 함수는 각 행마다 퀸을 배치하는데, isSafe 함수를 사용하여 현재 위치에 퀸을 배치할 수 있는지 여부를 확인합니다. 만약 현재 위치가 안전하면 퀸을 배치하고 다음 행으로 이동합니다. 만약 모든 행에 퀸을 성공적으로 배치하면 해당 배치를 결과에 추가합니다.