관리 메뉴

bright jazz music

백트래킹 알고리즘(backtracking algorithms) 본문

Algorithm&Data structure/JS alg.

백트래킹 알고리즘(backtracking algorithms)

bright jazz music 2024. 11. 11. 13:35

백트래킹은 가능한 모든 해결책을 탐색하면서, 현재 선택이 잘못된 방향으로 가고 있다고 판단되면 이전 단계로 돌아가서(백트랙) 다른 선택을 시도하는 알고리즘이다.

 

N-Queen 문제를 대표적인 예로 들 수 있다. N-Queen 문제는 체스판 위에 N개의 퀸을 배치하는 문제이다. 어떤 두 퀸도 같은 행, 열, 또는 대각선에 위치하지 않도록 하는 모든 가능한 배치를 찾는 것이다. 만약 같은 행, 열, 대각선에 하나라도 위치하게 된다면 일치한 퀸은 서로가 공격할 수 있는 상황에 노출된다. 이 문제에서는 각 행에 퀸을 배치하면서 이미 배치된 퀸과 충돌하지 않는 위치를 찾는다. 만약 충돌하지 않는 위치가 없다면 그 행에 대한 배치를 포기하고 이전 행으로 돌아가 다른 위치를 시도한다. 이러한 방식을 시도하면 모든 가능한 배치를 시도하지 않고도 문제의 해결책을 찾을 수 있다.

 

// N-Queen 문제: N x N 체스판에 N개의 퀸을 서로 공격할 수 없게 배치하는 문제
// 퀸은 가로, 세로, 대각선으로 움직일 수 있다
// 4x4 체스판의 경우 2가지 해답이 존재한다
function solveNQueens(n) {
   // Array(n).fill()로 n개의 행을 만들고, 
   // 각 행마다 map을 통해 n개의 열을 만들어 2차원 배열 생성
   // '.'은 빈칸, 'Q'는 퀸의 위치를 나타냄
   const board = Array(n).fill().map(() => Array(n).fill('.'));
   /*
       [
         [ '.', '.', '.', '.' ],
         [ '.', '.', '.', '.' ],
         [ '.', '.', '.', '.' ],
         [ '.', '.', '.', '.' ]
       ]
   */
   const solutions = [];
   
   // 퀸을 놓을 수 있는지 확인하는 함수
   // 이전 행들만 확인하면 됨 (현재 행 위쪽만 체크)
   // 1. 같은 열에 퀸이 있는지 체크
   // 2. 왼쪽 대각선에 퀸이 있는지 체크 (row-1, col-1 방향)
   // 3. 오른쪽 대각선에 퀸이 있는지 체크 (row-1, col+1 방향)
   // 세 방향 모두 퀸이 없어야 true 반환
   function isValid(row, col) {
       // 같은 열 체크
       for (let i = 0; i < row; i++) {
           if (board[i][col] === 'Q') return false;
       }
       
       // 왼쪽 대각선 체크
       for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
           if (board[i][j] === 'Q') return false;
       }
       
       // 오른쪽 대각선 체크
       for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
           if (board[i][j] === 'Q') return false;
       }
       
       return true;
   }
   
   // row는 현재 확인중인 행
   // n개의 퀸을 모두 배치했다면(row === n) 해답 배열에 추가
   // 각 행마다 가능한 모든 열(0 ~ n-1)에 퀸을 놓아보며 진행
   // 1. 현재 위치가 유효하면(isValid) 퀸 배치
   // 2. 다음 행으로 재귀 호출
   // 3. 백트래킹: 재귀 호출이 끝나면 현재 위치의 퀸 제거
   function backtrack(row) {
       // 기저 조건: 모든 행에 퀸을 배치했으면 해답 추가
       if (row === n) {
           solutions.push(board.map(row => row.join(''))); // .Q..
           return;
       }
       
        // 현재 행의 각 열에 퀸을 놓아보기
        for (let col = 0; col < n; col++) {
            if (isValid(row, col)) {    // 좌표를 방사형으로 체크했을 때 퀸이 없다면 true
                board[row][col] = 'Q';  // 퀸 배치
                backtrack(row + 1);     // 다음 행으로 진행 (재귀 호출로 인한 대기/waiting)
                                       // 이 지점에서 현재 프로세스가 대기 상태가 되고
                                       // 재귀적으로 다음 행들을 체크하는 작업 진행
                board[row][col] = '.';  // 재귀 호출 완료(해답 찾거나 실패) 후 퀸 제거(백트래킹)
                                       // 대기하던 작업이 완료된 후 현재 상태 초기화
            }
        }
   }
   
   // 백트래킹 시작: 0번 행부터 시작
   backtrack(0);
   return solutions;
}

// 시간 복잡도: O(N!)
// 각 행마다 N개의 열을 확인하고, 유효한 위치를 찾아 재귀적으로 진행
// 실제로는 가지치기(pruning)로 인해 N!보다는 적은 경우의 수를 확인

// 사용 예시
console.log(solveNQueens(4));
/*
출력 결과:
[
 [ '.Q..', '...Q', 'Q...', '..Q.' ],  // 아래와 같은 체스판을 의미
 [ '..Q.', 'Q...', '...Q', '.Q..' ]   // . Q . .
]                                     // . . . Q
                                      // Q . . .
                                      // . . Q .
                                      
 위 2차원 배열은 퀸을 겹치지 않고 배치하는 방법이 두 가지임을 의미한다.
 각 원소 배열이 하나의 솔루션을 의미한다.
*/

 

위 코드에서는, 체스판의 각 행을 순회하면서 퀸을 배치한다. 각 위치에서는 isValid 함수를 사용하여 해당 위치에 퀸을 배치할 수 있는지 확인한다. 퀸을 배치할 수 있는 위치를 찾으면 퀸을 배치하고 다음 행으로 이동한다. 만약 행의 모든 위치가 유효하지 않다면 이전 행으로 돌아가 퀸의 위치를 변경한다. 이러한 방식을 통해 모든 행에 퀸을 배치할 수 있는 모든 경우의 수를 찾을 수 있다.

 

구체적으로는,

1. 행(row) 기준 순회
   - 0번 행부터 시작해서 마지막 행까지 순차적으로 진행
   - 각 행에서는 모든 열(col)을 검사

2. 유효성 검사 (isValid 함수)
   - 현재 위치(row, col)에 퀸을 놓을 수 있는지 검사
   - 같은 열, 왼쪽 대각선, 오른쪽 대각선에 다른 퀸이 없어야 함

3. 백트래킹 과정
   if (isValid(row, col)) {
       board[row][col] = 'Q';     // 퀸 배치
       backtrack(row + 1);        // 다음 행으로 진행
       board[row][col] = '.';     // 실패시 퀸 제거하고 다음 열 시도
   }
   - 유효한 위치면 퀸을 배치하고 다음 행으로
   - 유효한 위치가 없거나 더 이상 진행이 불가능하면 이전 상태로 돌아가기
   - 이전 상태로 돌아갈 때는 배치했던 퀸을 제거(백트래킹)

4. 해답 찾기
   - 마지막 행(row === n)까지 도달하면 유효한 해답을 찾은 것
   - 찾은 해답을 solutions 배열에 저장

이것이 백트래킹의 핵심 매커니즘이다. 
"시도 -> 실패 -> 되돌아가기 -> 다시 시도" 의 과정을 반복하면서 모든 가능한 해답을 찾아내는 것이다.

 

 

 

 

예제2: 기사를 위한 자리

 

N-Queen 문제와 유사하다. knight는 L자 형태로 움직인다. 따라서 나이트가 서로 공격할 수 없다는 것은 어떤 두 나이트도 L자 형태의 움직임으로 이동할 수 있는 위치에 있지 않도록 배치해야 한다는 의미이다. 

 

// n x n 체스판에 나이트를 서로 공격할 수 없게 배치하는 문제
function solveKnight(n) {
    // n x n 크기의 2차원 배열 생성, '.'으로 초기화
    let board = Array(n)
        .fill()
        .map(() => Array(n).fill('.'));
    
    // 최종 해답을 저장할 배열
    let solution = [];
 
    // 나이트가 이동할 수 있는 8가지 방향 정의
    // dx, dy 쌍이 L자 형태의 이동을 표현
    let dx = [-2, -1, 1, 2, -2, -1, 1, 2];  // 행 방향 이동
    let dy = [1, 2, 2, 1, -1, -2, -2, -1];  // 열 방향 이동
 
    // 현재 위치(i,j)에 나이트를 놓을 수 있는지 확인하는 함수
    // 다른 나이트의 공격 범위에 있으면 true 반환
    function isAttack(i, j) {
        // 8방향을 모두 체크
        for(let k = 0; k < 8; k++) {
            let x = i + dx[k];
            let y = j + dy[k];
            // 체스판 범위 내에 있고, 해당 위치에 나이트('K')가 있는지 확인
            if(x >= 0 && y >= 0 && x < n && y < n && board[x][y] === 'K') {
                return true;  // 공격 가능한 나이트가 있음
            }
        }
        return false;  // 공격 가능한 나이트가 없음
    }
 
    // 백트래킹으로 나이트를 배치하는 함수
    // row: 현재 처리중인 행
    function backtrack(row) {
        // 기저 조건: 모든 행을 다 처리했으면 해답에 추가
        if(row === n) {
            solution.push(board.map(row => row.join('')));
            return;
        }
 
        // 현재 행의 각 열을 순회하면서 나이트 배치 시도
        for(let col = 0; col < n; col++) {
            if(!isAttack(row, col)) {       // 현재 위치에 나이트를 놓을 수 있다면
                board[row][col] = 'K';      // 나이트 배치
                backtrack(row + 1);         // 다음 행으로 진행 (재귀 호출로 인한 스레드 대기)
                board[row][col] = '.';      // 재귀 호출 완료 후 나이트 제거 (백트래킹)
            }
        }
    }
 
    // 0번 행부터 백트래킹 시작
    backtrack(0);
    return solution;
 }
 
 // 4x4 체스판에서 해답 찾기
 console.log(solveKnight(4));
/*
 [
    [ 'K...', 'K...', 'K...', 'K...' ],
    [ 'K...', 'K...', 'K...', '...K' ],
    [ 'K...', 'K...', '...K', 'K...' ],
    [ 'K...', 'K...', '...K', '..K.' ],
    [ 'K...', 'K...', '...K', '...K' ],
    [ 'K...', '.K..', 'K...', '.K..' ],
    [ 'K...', '.K..', 'K...', '...K' ],
    [ 'K...', '.K..', '..K.', '.K..' ],
    [ 'K...', '.K..', '..K.', '...K' ],
    [ 'K...', '...K', 'K...', 'K...' ],
    [ 'K...', '...K', 'K...', '.K..' ],
    [ 'K...', '...K', 'K...', '...K' ],
    [ 'K...', '...K', '..K.', '.K..' ],
    [ 'K...', '...K', '..K.', '...K' ],
    [ 'K...', '...K', '...K', 'K...' ],
    [ 'K...', '...K', '...K', '...K' ],
    [ '.K..', 'K...', '.K..', 'K...' ],
    [ '.K..', 'K...', '.K..', '..K.' ],
    [ '.K..', 'K...', '...K', 'K...' ],
    [ '.K..', 'K...', '...K', '..K.' ],
    [ '.K..', 'K...', '...K', '...K' ],
    [ '.K..', '.K..', '.K..', '.K..' ],
    [ '.K..', '..K.', '.K..', 'K...' ],
    [ '.K..', '..K.', '.K..', '..K.' ],
    [ '.K..', '..K.', '...K', 'K...' ],
    [ '.K..', '..K.', '...K', '..K.' ],
    [ '..K.', '.K..', 'K...', '.K..' ],
    [ '..K.', '.K..', 'K...', '...K' ],
    [ '..K.', '.K..', '..K.', '.K..' ],
    [ '..K.', '.K..', '..K.', '...K' ],
    [ '..K.', '..K.', '..K.', '..K.' ],
    [ '..K.', '...K', 'K...', 'K...' ],
    [ '..K.', '...K', 'K...', '.K..' ],
    [ '..K.', '...K', 'K...', '...K' ],
    [ '..K.', '...K', '..K.', '.K..' ],
    [ '..K.', '...K', '..K.', '...K' ],
    [ '...K', 'K...', 'K...', 'K...' ],
    [ '...K', 'K...', 'K...', '...K' ],
    [ '...K', 'K...', '.K..', 'K...' ],
    [ '...K', 'K...', '.K..', '..K.' ],
    [ '...K', 'K...', '...K', 'K...' ],
    [ '...K', 'K...', '...K', '..K.' ],
    [ '...K', 'K...', '...K', '...K' ],
    [ '...K', '..K.', '.K..', 'K...' ],
    [ '...K', '..K.', '.K..', '..K.' ],
    [ '...K', '..K.', '...K', 'K...' ],
    [ '...K', '..K.', '...K', '..K.' ],
    [ '...K', '...K', 'K...', 'K...' ],
    [ '...K', '...K', 'K...', '.K..' ],
    [ '...K', '...K', 'K...', '...K' ],
    [ '...K', '...K', '...K', 'K...' ],
    [ '...K', '...K', '...K', '...K' ]
  ]
    */