백준 9663 N-Queen

문제

제한 사항

입출력 예

풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim();
const N = +input;
const sol = (N) => {
  const rows = new Array(N).fill(0); // 행
  let cnt = 0;

  const check = (row, column) => {
    for (let i = 0; i < row; i++) {
      // 열의 값이 같으면 안됨.
      if (column === rows[i]) return false;
      // 열의 차이가 행의 차이와 같을 때
      if (Math.abs(column - rows[i]) === row - i) return false;
    }
    return true;
  };

  function dfs(L) {
    if (L === N) {
      cnt++;
      return;
    }
    for (let i = 0; i < N; i++) {
      // 행을 기준으로 배열을 삼아서 i값은 열이 된다.
      // L행 i열에 값이 올 수 있는 지 체크
      if (check(L, i)) {
        // L열에 i행에 위치 시킨다.
        rows[L] = i;
        // 열을 높여준다.
        dfs(L + 1);
        rows[L] = 0;
      }
    }
  }

  dfs(0);
  return cnt;
};

console.log(sol(N));

백트래킹을 해야하는 것과 과정은 알겠으나 가지치기하는 코드를 이해하기가 여러워 다른 글을 참고했다.

우선 퀸의 움직임을 이해해야 한다. 퀸은 상, 하, 좌, 우, 대각선으로 무한정 이동이 가능하다. 퀀은 서로 다른 행과열에 위치해야 하므로, 행과 열 중 하나만 기준으로 잡는다.

나는 행을 기준으로 잡았다. 위 그림의 예시를 들면 행 배열의 상태가 [1,3,0,2] 가된다. 인덱스는 행의 이름이 되고 값은 열의 위치가 되는 것이다.

0행에서 퀸의 열 위치를 정하고, 1행에서 퀸의 열 위치를 저장하는 과정반복하고 4개가 조건에 맞게 배치되면 카운트를 증가시키면 된다.

퀸을 위치시킬 때 위치시키고자 하는 열에, 이미 다른 행에서 퀸을 위치시켰다면 그 위치는 불가능하다. 또한 대각선에도 퀸이 위치할 수 없다.

이 상황을 이해하고 주석을 잘 읽어보자.