[알고리즘] Backtracking, N-Queen 문제

Backtracking이란??

해(답)을 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아가서 다시 해를 찾아가는 기법을 의미한다.

즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적이다.

이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다.

주로 DFS 등 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤, 그 이전으로 돌아가서 다시 다른 경우를 탐색하게 구현할 수 있다.

백트래킹 기법의 유망성 판단

어떤 노드의 유망성, 즉 해가 될 만한지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전(부모)로 돌아가(Backtracking) 다음 자식 노드로 갑니다.

• 유망하다(promising) : 해가 될 가능성이 있는 경우
• 가지치기(pruning): 유망하지 않은 노드에 가지 않는 것

예시 : N-Queen 문제

• N*N 체스판에 N개의 퀸을 배치할 수 있는 경우의 수를 센다.
• 퀸은 상하좌우, 대각선 방향으로 거리 제한없이 이동될 수 있다.
• N=8인 경우, 경우의 수는 다음과 같다.
  • 64 * 63 * ... * 57 = 178,462,987,637,760
  • C 기준 1초에 1억 번을 연산하므로 모든 경우의 수를 탐색하는데 약 20.6시간이 소요된다.

여기서 Backtracking을 사용한다면

이런식으로 하나씩 가지치기를 함으로써 풀어갈 수 있다.

Typescript로 코드를 구현하자면

function NQueen(n: number) {
  // 통과한 개수
  let count = 0;
  // 답을 넣기 위한 기능
  let answer: number[][] = [];

  // DFS 구현
  const dfs = function (board: number[], row: number) {
    // row의 인덱스가 n-1까지 도달한 경우
    if (row === n - 1) {
      count++;
      // 스프레드 문법을 쓴 이유는
      // board 자체를 넣는 경우에는, board 내부의 주소 값이 계속 변하기 때문에 답안이 틀려진다.
      answer.push([...board]);
    } else {
      // col을 n-1개까지 반복하면서 대입한다.
      for (let i = 0; i < n; i++) {
        board[row + 1] = i;
        // 만약 isValid 함수가 True라면 DFS를 다시 진행
        if (isValid(board, row + 1)) dfs(board, row + 1);
      }
    }
  };

  // Backtracking 메서드
  const isValid = function (board: number[], row: number): boolean {
    for (let i = 0; i < row; i++) {
      if (
        // 열이 같은 경우 탈락
        board[i] === board[row] ||
        // 대각선인 경우 탈락
        Math.abs(board[i] - board[row]) === Math.abs(i - row)
      ) {
        return false;
      }
    }
    return true;
  };

  for (let i = 0; i < n; i++) {
    // 새로운 board 생성
    const board = new Array(n).fill(-1);
    // 첫번째 row의 column을 선택
    board[0] = i;
    dfs(board, 0);
  }

  return { count, answer };
}

 

 

 

참조

https://chanhuiseok.github.io/posts/baek-1/

https://velog.io/@longroadhome/프로그래머스-LV.3-최고의-집합-JS-2xs6gra3