[백준]9663번 'N-Queen' 문제 풀이 - JavaScript

[백준]9663번 'N-Queen' 문제 풀이 - JavaScript

문제

N-Queen 문제는 크기가 N x N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 1

8

예제 출력 1

92

👉 풀이 코드

const fs = require('fs');
const file = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = fs.readFileSync(file).toString().trim();

const n = Number(input);
const queens = [];
let count = 0;

function possible(x, y) {
  for (const [a, b] of queens) {
    if (a === x || b === y) return false;
    if (Math.abs(a - x) === Math.abs(b - y)) return false;
  }
  return true;
}

function dfs(row) {
  if (row === n) {
    count++;
    return;
  }
  for (let i = 0; i < n; i++) {
    if (!possible(row, i)) continue;
    queens.push([row, i]);
    dfs(row + 1);
    queens.pop();
  }
}
dfs(0);

console.log(count);

👉 풀이 해설

퀸을 놓을 수 있는 방법은 A퀸이 존재한다면 A퀸에 행과 열, 그리고 대각선 위치가 아닌 위치에 놓을 수 있다.

N개의 퀸을 놓기 위해서는 각 행 마다 1개씩 놓아야 N개의 퀸을 놓을 수 있다.

반응형

N = 4라고 가정을 해보자.

	Q
			Q
Q
		Q

이런 식으로 각 행에 하나씩 Q이 들어가야 N x N에 N개의 퀸을 놓을 수 있다는 것을 볼 수 있다.

이 문제는 이렇게 놓을 수 있는 경우의 수를 찾는 것이다.

매 재귀함수마다 N x N의 모든 위치를 볼 필요는 없다.

맨 처음 행(row)부터 차례대로 퀸을 놓는다고 생각하면 탐색해야 하는 범위를 줄일 수 있다.

이 문제는 가능한 조합을 계산하는 것이기 때문에 현재 행의 이전 행으로 돌아갈 필요가 없다.

 

즉, 이 문제는 백트래킹으로 풀 수 있다.

특정 위치(노드)로 갈 수 있는지를 판별하면 되는데, 이때 퀸을 놓을 수 있는 위치인가 아닌가를 판별해야 한다.

현재 놓으려는 퀸이 기존에 있는 퀸의 위치와 비교하며

1. 같은 행에 있는지 확인: (x1 == x2) || (y1 == y2)
2. 대각선에 있는지 확인: abs(x1 - x2) == abs(y1 - y2)

대각선에 있는지 확인하는 부분에서 이런 계산 방법이 나온 이유는 아래와 같다.

		Q
	Q

A퀸 : 0번째 행, 2번째 열에 퀸이 놓여 있다. (0, 2)

B퀸: 1번째 행,  1번째 열에 퀸을 놓으려고 한다. (1, 1)

abs(0 - 1) = 1

==

abs(2 - 1) = 1

놓인 퀸과 놓으려는 퀸의 행끼리 차이와 열 끼리 차이의 값이 같다는 걸 확인할 수 있다.

 

자, 그럼 이제 구현하기만 하면 된다.

입출력을 n변수에 담아주고, 현재까지 놓인 퀸들의 위치를 저장할 queen 배열을 빈 배열로 초기화해준다.

경우의 수를 담을 count 변수도 선언해 준다.

 

possibe 함수는 놓으려는 퀸의 행과 열을 x, y로 받는다.

지금껏 놓인 퀸의 위치를 담은 queens 배열을 순회하면서 위에서 말한 놓을 수 있는 위치인지 아닌지를 판별하며 놓을 수 없다면 false, 놓을 수 있다면 ture를 반환해 준다.

 

dfs함수는 마지막 행까지 갔다면 N개의 퀸을 놓았다는 것이기 때문에 count를 증가시켜 준다.

마지막 행까지 가지 않았다면 0부터 n까지 반복문을 수행한다.

놓으려는 퀸의 행(row)과 열(i)를 possible 함수로 넘겨주고 boolean값을 받는다.

놓을 수 없다면 다음 열로 이동(continue)시켜주고 놓을 수 있다면 queens 배열에 놓을 위치를 담아주고 재귀함수를 호출하며 다음 행(row)으로 넘어간다 (row + 1)

재귀 함수가 끝나면 queens배열에 놓았던 퀸의 위치를 빼준다.

 

이렇게 가짓수를 쳐가면서 하나하나 경우의 수를 찾아서 마지막에 count를 출력한다.