자료구조&알고리즘_백트래킹

백트래킹

• 모든 경우의 수를 탐색하는 알고리즘
• DFS나 BFS이용
• 효율을 위해 탐색하지 않아도 되는 곳을 미리 막는 것을 가지치기라고 한다.
• 자바스크립트는 재귀 효율이 안좋다. 때문에 DFS일 경우 Stack을 이용하는 것이 좋다.
• 순환(Cycle)이 발생할 수 있다면 BFS를 이용하는 것이 좋다.

가지치기 🎄

백트래킹의 핵심이라고 할 수 있고 얼마나 잘 하느냐에 따라 효율성을 결정한다.

가지치기 방법
1. 모든 경우의 수를 찾을 수 있도록 코딩
2. 특정한 조건을 만족하는 것만 탐색하고, 나머지는 탐색하지 않도록 조건문 작성
3. 절대로 답이 될 수 없는 것은 탐색을 종료한다.

코드구현 (N-Queen)

문제링크

전략

가지치기를 할 수 있는 경우는 다음과 같다.
1. 퀸을 둔 행은 가지치기 한다.
2. 퀸을 둔 열은 가지치기 한다.
3. 퀸을 둔 대각선 왼쪽, 오른쪽은 가지치기 한다.

가지치기 조건을 찾은 것은 좋지만 가지치기를 위해 행과 열, 대각선을 루프를 통해 검사하게 되면 성능을 크게 낭비하게 된다.
그래서 최대한 적은 비용으로 가지치기를 하기 위해 1차원 배열을 사용한다.

• 배열의 index는 행의 위치, 해당 index의 value는 열의 위치
  ex)queen[2] = 1은 체스판 위에서 두 번째 줄, 첫 번째 칸에 해당한다.

• 한 index에 여러 value를 둘 수 없기에 행은 자연스럽게 가지치기 된다.

• index가 같다면 둘 수 없다. 같다면 가지치기 한다.

• 행, 열에 대한 차가 같다면 대각선에 있다는 뜻이므로 가지치기 한다.
  ex)1부터 시작한다고 가정할 때 queen[3] = 2, queen[1] = 4일 때 행에 대한 차 3 - 1과 열에 대한 차 4 - 2는 같기 때문에 대각선에 있다는 뜻이다. (절대값으로 계산하면 왼쪽, 오른쪽 둘다 체크 가능하다)

이런 방식으로 검사 비용을 아낄 수 있다.

function check(queen, row) {
  // 이전까지 두었던 퀸의 위치를 확인한다.
  for (let i = 0; i < row; i += 1) {
      // 행의 위치와 대각선의 위치를 체크한다.
      if (queen[i] === queen[row] || Math.abs(queen[i] - queen[row]) === row - i) {
          return false; // 둘 수 없다면 false
      }
  }
  
  return true; // 모두 통과되면 true
}

function search(queen, row) {
  const n = queen.length;
  let count = 0;
  
  if (n === row) { // 체스판 끝에 도달했다면.. 재귀의 탈출 조건
      return 1;
  }
  
  for (let col = 0; col < n; col += 1) { // 0부터 n까지 열을 돌면 둘 수 있게 만든다.
      queen[row] = col; // 우선 퀸을 둔다
      if (check(queen, row)) { // 퀸을 둘 수 있다면..
          count += search(queen, row + 1); // 다음 행으로 이동!
      }
  }
  
  return count;
}

function solution(n) {
  // 미리 n개 만큼의 배열을 초기화한다. 0번 행부터 시작한다.
  return search(Array.from({ length: n }, () => 0), 0);
}

출처

프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.

프로그래머스 데브코스