[백준] 9663번 N-Queen - JavaScript(NodeJS)

문제

9663번: N-Queen

풀이

가장 중요한 문제의 조건은 퀸의 움직임이다.

 

퀸은 한 번 움직일 때 자기 위치에서 상하좌우+대각선 중 한 방향으로 무한정 이동 가능하다.

따라서 퀸이 서로 공격을 할 수 없는 예시를 그려보면 아래 그림과 같다.

 

이외에도 여러 경우가 있을테니, N이 주어졌을 때 퀸을 놓는 경우의 수를 구하면 된다.

 

풀이 방향

퀸의 움직임을 알고나면 문제가 쉬워진다.

 

N개를 배치해야 하므로 DFS를 이용해 문제를 풀어보자.

 

DFS에서 N x N를 모두 조회할 필요는 없다.

 

퀸은 서로 다른 행과 열에 위치해야 하므로, 행이나 열 중 하나를 기준으로 잡아본다.

크기 N인 배열을 선언하고, 이 배열의 0번 인덱스 값은 0행에서 위치한 퀸의 열번호를 의미한다.

 

예시 그림을 배열로 표현하면, [2, 0, 3, 1] 이다.

 

이렇게 행을 기준으로 했다면
1행에서 퀸이 위치해야 할 열을 정하고, 2행에서 퀸이 위치해야 할 열을 정한다.
성공적으로 N행까지 퀸을 위치시켰다면 카운트를 증가시키면 된다.

 

퀸을 위치시킬 때, 퀸의 특성을 고려해준다.

퀸을 위치시키고자 하는 열에, 이미 다른 행에서 퀸을 위치시켰다면 그 위치는 불가능하며
또한 위치시키고자 하는 열의 대각선에 퀸이 위치해도 불가능함을 고려하면 된다.

 

코드를 보자.

 

코드

const sol = (N) => {
  const row = new Array(N).fill(0);
  let cnt = 0;

  function isPossible(L, X) { // L행 X열에 퀸을 둘 수 있는지 판단하기 위해 0 ~ L-1행까지 상하좌우 + 대각선까지 조회.
    for (let i = 0; i < L; i++) {
      if (X === row[i]) return false;
      if (Math.abs(X - row[i]) === L - i) return false;
    }
    return true;
  }

  function dfs(L) {
    if (L === N) {
      cnt++;
      return;
    }
    for (let i = 0; i < N; i++) {
      if (isPossible(L)) { // L행 i열에 둘 수 있다면 실행.
        row[L]=i;
        dfs(L + 1);
      }
    }
  }

  dfs(0);
  return cnt;
};

// 백준에서 입력을 받는 코드
const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    console.log(sol(+line));
  })
  .on("close", () => {
    process.exit();
  });