백트래킹 (Backtracking)

백트래킹은 문제를 해결하기 위한 탐색 알고리즘으로, 가능한 모든 해를 탐색하는 과정에서 잘못된 경로로 들어서면 그 즉시 되돌아가서 다른 경로를 탐색하는 방법입니다. 이를 통해 문제의 최적해를 찾거나, 문제의 조건을 만족하는 해를 구할 수 있습니다. 백트래킹은 주로 조합 탐색, 그래프 탐색, 퍼즐 문제 해결 등에 사용됩니다. 대표적인 문제로는 N-퀸 문제와 부분 집합 문제가 있습니다.

1. N-퀸 문제 (N-Queens Problem)

N-퀸 문제는 체스판 위에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제입니다. 퀸은 가로, 세로, 대각선 방향으로 공격할 수 있기 때문에, 퀸들이 서로 공격하지 않도록 배치하는 것이 핵심입니다. 백트래킹을 사용하여 문제의 가능한 모든 경우를 탐색하면서 조건을 만족하는 해를 찾습니다.

N-퀸 문제의 동작 원리

첫 번째 행에서 퀸을 놓을 수 있는 위치를 찾고, 퀸을 놓습니다.
다음 행으로 이동하여, 퀸이 다른 퀸들과 공격 범위에 있지 않은 위치를 찾습니다.
만약 조건을 만족하는 위치를 찾을 수 없으면, 이전 행으로 돌아가서 다른 위치에 퀸을 놓아봅니다.
이 과정을 반복하여 모든 퀸이 배치되면 문제의 해를 구한 것입니다.

N-퀸 문제 백트래킹 예제 코드


// N-퀸 문제 (백트래킹) - JavaScript
function solveNQueens(n) {
    let result = [];
    let board = Array.from({ length: n }, () => Array(n).fill('.'));

    function isSafe(row, col) {
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q' ||  // 같은 열에 퀸이 있는지 확인
                (col - (row - i) >= 0 && board[i][col - (row - i)] === 'Q') ||  // 왼쪽 대각선
                (col + (row - i) < n && board[i][col + (row - i)] === 'Q')) {  // 오른쪽 대각선
                return false;
            }
        }
        return true;
    }

    function placeQueens(row) {
        if (row === n) {
            result.push(board.map(r => r.join('')));
            return;
        }
        for (let col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                board[row][col] = 'Q';
                placeQueens(row + 1);
                board[row][col] = '.';  // 백트래킹
            }
        }
    }

    placeQueens(0);
    return result;
}

console.log(solveNQueens(4));
/*
출력:
[
    [
        ".Q..",
        "...Q",
        "Q...",
        "..Q."
    ],
    [
        "..Q.",
        "Q...",
        "...Q",
        ".Q.."
    ]
]
*/

이 코드에서는 재귀적으로 퀸을 배치하면서 조건을 만족하지 않으면 되돌아가는 방식을 사용합니다. 시간 복잡도는 최악의 경우 O(n!)로 매우 비효율적일 수 있으나, 백트래킹을 통해 불필요한 경로를 배제하여 성능을 개선할 수 있습니다.

2. 부분 집합 문제 (Subset Problem)

부분 집합 문제는 주어진 집합에서 가능한 모든 부분 집합을 구하는 문제입니다. 예를 들어, 집합 {1, 2, 3}이 주어졌을 때, 그 부분 집합은 {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, {}입니다. 백트래킹을 사용하여 가능한 모든 부분 집합을 구할 수 있습니다.

부분 집합 문제의 동작 원리

현재 선택한 원소를 포함하는 경우와 포함하지 않는 경우로 나누어 탐색합니다.
각 원소에 대해 포함 여부를 결정하고, 이를 통해 모든 가능한 조합을 생성합니다.
재귀적으로 진행하며, 탐색 도중 필요 없는 경로는 제외합니다.

부분 집합 문제 백트래킹 예제 코드


// 부분 집합 문제 (백트래킹) - JavaScript
function subsets(nums) {
    let result = [];

    function generateSubset(index, current) {
        if (index === nums.length) {
            result.push([...current]);
            return;
        }
        // 현재 원소를 포함하지 않는 경우
        generateSubset(index + 1, current);
        // 현재 원소를 포함하는 경우
        current.push(nums[index]);
        generateSubset(index + 1, current);
        current.pop();  // 백트래킹
    }

    generateSubset(0, []);
    return result;
}

console.log(subsets([1, 2, 3]));
/*
출력:
[
    [],         // 공집합
    [3],
    [2],
    [2, 3],
    [1],
    [1, 3],
    [1, 2],
    [1, 2, 3]
]
*/

이 코드는 재귀적으로 각 원소를 포함하거나 포함하지 않는 방식으로 부분 집합을 생성합니다. 부분 집합 문제는 O(2^n)의 시간 복잡도를 가지며, n개의 원소에 대해 2^n개의 부분 집합을 생성할 수 있습니다.

백트래킹과 가지치기

백트래킹 알고리즘에서는 불필요한 탐색 경로를 조기에 배제하는 '가지치기(pruning)' 기법이 매우 중요합니다. 이를 통해 탐색 공간을 크게 줄일 수 있습니다. 예를 들어, N-퀸 문제에서 같은 열이나 대각선에 퀸이 있는 경우 해당 경로를 더 이상 탐색하지 않고 되돌아가 다른 경로를 탐색하는 방식으로 가지치기를 할 수 있습니다. 가지치기를 적절히 사용하면 백트래킹의 성능을 크게 개선할 수 있습니다.

백트래킹의 응용

백트래킹은 N-퀸 문제나 부분 집합 문제뿐만 아니라 다양한 문제에 응용될 수 있습니다. 대표적인 예로는 퍼즐 문제(예: 스도쿠), 그래프 탐색, 조합 최적화 문제 등이 있으며, 백트래킹을 통해 탐색해야 할 공간을 줄이고 효율적으로 문제를 해결할 수 있습니다.

결론

백트래킹은 가능한 모든 경우를 탐색하면서 조건을 만족하지 않는 경우를 빠르게 배제하여 문제를 해결하는 강력한 기법입니다. N-퀸 문제와 부분 집합 문제는 백트래킹의 대표적인 예이며, 이를 통해 복잡한 문제를 효율적으로 해결할 수 있습니다. 백트래킹을 적용할 때, 불필요한 경로를 제외하는 가지치기 기법을 활용하여 성능을 더욱 최적화할 수 있습니다.

DAILY IS COMING

백트래킹 (Backtracking) 요약