백준 9663 N-Queen (node.js)

문제

https://www.acmicpc.net/problem/9663

 

문제 해석

이 문제는 백 트래킹의 대표적인 문제이다.

DFS 기반으로 트리를 그리면서 풀 수 있는 문제이며, 밑으로 트리를 생성할 때 조건을 확인하는 식으로 풀면 된다.

 

여기서 조건은 현재 퀸의 위치를 기준으로 위 아래 대각선을 확인해야 한다.

 

열의 위치는 v1에 표시를 하며, (i, j)에서 j의 값만을 기록하면 된다.

왼쪽 위로 올라가는 대각선의 경우는 i - j 가 일정하기 때문에 v2 [i - j]로 작성하되 - 가 되면 안 되기 때문에 전체길이를 더해준다.

오른쪽 위로 올라가는 대각선의 경우 (i, j)의 값이 모두 동일하기 때문에 v3 [i+j] 식으로 기록해 준다.

 

이후 각 조건에서 L과 N이 동일하면 answer를 더하는 방식으로 해결하였다.

 

풀이

const filePath = process.platform === "linux" ? "dev/stdin" : "../test.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

function solution(input) {
  const N = Number(input);
  const v1 = Array.from({ length: N + 1 }, () => 0);
  const v2 = Array.from({ length: N * 2 - 1 }, () => 0);
  const v3 = Array.from({ length: N * 2 - 1 }, () => 0);
  let answer = 0;

  function DFS(L) {
    if (L === N) {
      answer++;
      return;
    }

    for (let i = 0; i < N; i++) {
      if (v1[i] === 0 && v2[N + L - i - 1] === 0 && v3[L + i] === 0) {
        v1[i] = v2[N + L - i - 1] = v3[L + i] = 1;
        DFS(L + 1);
        v1[i] = v2[N + L - i - 1] = v3[L + i] = 0;
      }
    }
  }

  DFS(0);
  return answer;
}

console.log(solution(input));

 

 

끝