🎯 백트래킹

백트래킹(BackTracking)은 해를 찾아가는 도중, 지금의 경로가 정답이 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아가는 방법이다. 백트래킹은 DFS 알고리즘을 사용하는데 기존 DFS는 엄청나게 큰 경우의 수라면 모든 케이스를 다 순회해야 하기 때문에 비효율적인 방법을 대체하고자 등장한 알고리즘이다.

즉, 코딩에서는 반복문의 횟수까지 줄일 수 있는 아주 효율적인 알고리즘이다. 이를 흔한 용어로 가지 치기리고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미로 불린다.

일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수도 있다. 즉 가지 치기를 얼마나 잘하느냐에 따라 효율성이 결정된다.

정리하자면, 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다. 즉 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것을 백트래킹이라고 생각하면 된다.

🎯 예제로 확인하는 백트래킹 (JS)

문제의 난이도는 그렇게 높다고 느껴지지 않았는데 생각할 부분이 많아서 정말 많이 헷갈렸다. 특히 재귀함수를 사용한다는 것이 아직은 많이 낯설게 느껴졌다. 정말 중요한 점은 찾고자 하는 포인트가 발견되었을 때는 반드시 return문을 사용하여 해당 재귀함수가 종료되게끔 해야한다.

💎 N-Queen (BOJ 9663)

👉 문제 확인하기 : N-Queen

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString();
const NUMBER = Number(input);

let board = [];
let count = 0;

function isPossible(row) {
  for (let i = 0; i < row; i += 1) {
    if (board[row] === board[i]) return true;

    if (Math.abs(board[row] - board[i]) === row - i) return true;
  }
  return false;
}

function backTracking(row) {
  if (row === NUMBER) {
    count += 1;
    return;
  }

  for (let i = 0; i < NUMBER; i += 1) {
    board[row] = i;
    if (!isPossible(row)) backTracking(row + 1);
  }
}

backTracking(0);
console.log(count);

💎 N과 M (9) (BOJ 15663)

👉 문제 확인하기 : N과 M (9)

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [N, M] = input.shift().split(' ').map(Number);
const numberArr = input
  .shift()
  .split(' ')
  .map(Number)
  .sort((a, b) => a - b);
let visited = Array(N).fill(false);

let answer = [];
let result = [];

function backTrack() {
  if (answer.length === M) {
    result.push(answer.join(' '));
    return; // 어떻게 재귀함수를 탈출하느냐가 중요 포인트이다
  }

  for (let i = 0; i < N; i += 1) {
    if (!visited[i]) {
      answer.push(numberArr[i]);
      visited[i] = true;
      backTrack();
      visited[i] = false;
      answer.pop();
    }
  }
}

backTrack(0);

const RESULT = new Set(result);
console.log([...RESULT].join('\n'));

📑 HSAT 정기 문제로 백트래킹 연습하기

👉 문제 확인하기 : 순서대로 방문하기

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [N, M] = input.shift().split(' ').map(Number);
let board = [];
for (let i = 0; i < N; i += 1) {
  board.push(input.shift().split(' ').map(Number));
}

let place = [];
input.forEach((value) => place.push(value.split(' ').map(Number)));

const dX = [-1, 1, 0, 0];
const dY = [0, 0, -1, 1];

let visited = Array.from({ length: N }, () => Array(N).fill(false));
let result = [];

function DFS(points, depth) {
  const [X, Y] = points;

  if (depth === M) {
    result.push([X, Y]);
    return;
  }

  if (place[depth][0] === X && place[depth][1] === Y) {
    DFS(points, depth + 1);
    return;
  }

  visited[X - 1][Y - 1] = true;

  for (let i = 0; i < 4; i += 1) {
    const [aX, aY] = [X - 1 + dX[i], Y - 1 + dY[i]];

    if (aX < 0 || aX >= N || aY < 0 || aY >= N || board[aX][aY] === 1 || visited[aX][aY]) continue;
    else {
      DFS([aX + 1, aY + 1], depth);
    }
  }

  visited[X - 1][Y - 1] = false;
}

DFS(place[0], 0);
console.log(result.length);