[알고리즘] 백트래킹 (JS)

📌 참고 사이트

퇴각검색 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

퇴각검색 - 위키백과, 우리 모두의 백과사전

 

알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제 | ChanBLOG (chanhuiseok.github.io)

알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제

 

https://velog.io/@pul8219/JS-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9BackTracking

[JS] 백트래킹(BackTracking)

 

 

 

📋 백트래킹 (backtracking)

📍 백트래킹의 특징

➡️ 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것으로, 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기를 한다.

 

➡️ 탐색 중에 오답을 만나면 이전 분기점으로 돌아간다. 시도해보지 않은 다른 해결 방법이 있으면 시도하고, 해결 방법이 없으면 더 이전의 분기점으로 돌아간다. 모든 트리의 노드를 검사해도 답을 찾지 못할 경우 해결책은 없는 것이 된다.

 

➡️ 보통의 경우 재귀 함수로 구현된다. DFS 등으로 모든 경우의 수를 탐색하는 과정에서 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그런 경우에 해당하면 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현한다.

 

 

📍 백트래킹 적용해 보기

백준 9663번 N-Queen 문제를 백트래킹 기법을 이용해 풀어보겠다.

 

9663번: N-Queen (acmicpc.net)

9663번: N-Queen

 

✏️ 문제

크기가 N x N인 체스판 위에 퀸 N개를 서로 공격할 수 없도록 놓는 모든 경우의 수의 개수를 구하는 문제이다.

 

❓ 퀸이 서로 공격할 수 없다는 조건

체스에서 퀸이 서로 공격할 수 없다는 조건은 퀸이 놓였을 때 퀸 자신을 기준으로 가로, 세로, 대각성 방향에는 아무것도 놓여 있으면 안된다.

 

❓ 이 문제가 백트래킹인 이유

 

let n = Number(require("fs").readFileSync("./input.txt"));

let result = 0; // 퀸을 놓을 수 있는 모든 경우의 수
let board = []; // 체스판 배열, 이 배열의 인덱스는 행이 되고, 값은 열이 된다.
// (배열의 인덱스가 행이 되므로, 애초에 같은 행에 놓일 수 없게 된다.)

// 충돌이 발생하는지 확인
function hasConflict(x) {
  // 현재 행의 이전 행을 돌면서
  for (let i = 0; i < x; i++) {
    // 이전 행에서 현재 행에서의 퀸과 같은 열에 존재하는 퀸이 있다면
    if (board[i] === board[x]) {
      // 충돌이 발생한 것이므로 true 반환
      return true;
    }
    // 이전 퀸이 대각선에 위치하는지도 확인해야 함
    if (Math.abs(board[x] - board[i]) === x - i) {
      // 떨어져 있는 열의 거리와 행의 거리가 같으면 대각선에 위치하여 충돌하므로 true 반환
      return true;
    }
  }
  // 위 조건들을 모두 그냥 지나치면 충돌이 발생하지 않는 경우이므로 false 반환
  return false;
}

// board에 퀸을 등록하고, 충돌이 일어나지 않으면 행 증가하는 함수
function findNQueen(row) {
  // 마지막 행까지 진행되었다는 것은 경우의 수를 찾았다는 의미이므로 result 값 증가
  if (row === n) {
    result++;
    return;
  }
  // 열을 하나씩 증가시키면서 돌기
  for (let col = 0; col < n; col++) {
    // 현재 행에 대한 열을 board에 저장
    board[row] = col;
    // 충돌이 일어나지 않는다면 (충돌이 일어나는지는 매 열마다 확인)
    if (!hasConflict(row)) {
      // 행을 증가시켜 재귀적으로 실행
      findNQueen(row + 1);
    }
  }
}

// 항상 0행부터 시작하여 입력받은 n - 1번째 행까지 진행
findNQueen(0);
console.log(result);

 

이 문제가 백트래킹인 이유는 충돌이 발생하는 경우 findNQueen(row + 1)을 하여 더 깊은 레벨의 노드로 탐색이 진행되지 않고 가지치기가 된다는 점에서이다. 충돌이 발생하면 다음 열(형제 노드)에 대하여 탐색하게 된다.

반면 충돌이 발생하지 않는 경우에는 findNQueen(row + 1)이 진행되어 더 깊은 레벨의 노드에서 경우의 수를 계속 탐색해 나가게 된다.

행을 인덱스로 사용하고, 열을 값으로 사용하고, 대각선에 위치하는지는 행간 거리와 열간 거리가 일치하는지를 통해 판단하는 식으로 진행하여 일차원 배열로 해결 가능하도록 하는 아이디어가 핵심인 문제이다. (물론 혼자서 저 아이디어 생각해내지 못했음.....ㅜ)

아래 사진을 보면 이해가 가능할 것이다.

 

출처 : https://jehwanyoo.net/2022/01/26/n-queen-%EB%AC%B8%EC%A0%9C-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9/