🔴 문제
🟡 Sol
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const n = Number(fs.readFileSync(path));
let answer = 0;
const cols = Array(n).fill(false);
const d1 = Array(2 * n - 1).fill(false);
const d2 = Array(2 * n - 1).fill(false);
const bt = (x) => {
if (x === n) {
answer += 1;
return;
}
for (let y = 0; y < n; y++) {
if (cols[y] || d1[x + y] || d2[x - y + n - 1]) continue;
cols[y] = d1[x + y] = d2[x - y + n - 1] = true;
bt(x + 1);
cols[y] = d1[x + y] = d2[x - y + n - 1] = false;
}
};
bt(0);
console.log(answer);🟢 풀이
⏰ 소요한 시간 : -
처음에는 감이 오지 않아서 유튜브 풀이를 3분까지 보고 사고의 방향을 정한 뒤에 아래와 같이 풀이했다. (시간초과)
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const n = Number(fs.readFileSync(path));
let answer = 0;
let map;
const check = (x, y) => {
let nx, ny;
for (let i = 0; i < n; i++) {
// 같은 줄이나 행에 하나라도 퀸이 놓여있으면 false
if (map[x][i] || map[i][y]) return false;
}
// 대각선 확인
for (let i = 1; i < n; i++) {
nx = x + i;
ny = y + i;
if (nx >= 0 && ny >= 0 && nx < n && ny < n && map[nx][ny]) return false;
nx = x - i;
ny = y - i;
if (nx >= 0 && ny >= 0 && nx < n && ny < n && map[nx][ny]) return false;
nx = x - i;
ny = y + i;
if (nx >= 0 && ny >= 0 && nx < n && ny < n && map[nx][ny]) return false;
nx = x + i;
ny = y - i;
if (nx >= 0 && ny >= 0 && nx < n && ny < n && map[nx][ny]) return false;
}
return true;
};
const bt = (selected, target) => {
if (selected.length === n) answer += 1;
for (let i = target + 1; i < n * n; i++) {
const x = Math.floor(i / n);
const y = i % n;
// 밟을 수 있다면
if (check(x, y)) {
map[x][y] = true;
const newSelected = selected.map((it) => [...it]);
newSelected.push([x, y]);
bt(newSelected, i);
map[x][y] = false;
}
}
};
for (let i = 0; i < n; i++) {
map = Array.from({ length: n }, () => Array(n).fill(false));
map[0][i] = true;
bt([[0, i]], 0);
}
console.log(answer);당연히 시간초과 무려 시간복잡도가 n의 3제곱이다...
그래서 지피티한테 물어보고 풀이 영상도 봤다.(체스규칙도 몰랐었다.)
위 정답코드는 지피티 풀이를 보고 이해한 코드다. 근데 유튜브랑 풀이방식 동일한듯
이 문제에서는 한 줄에서 하나의 위치에만 퀸을 놓을 수 있다라는 발상으로부터 풀이가 시작된다. n는 0부터 1, 2, 3, 4, ... n-1 까지 총 n개를 선택 해야하고 x가 n이 되는 순간 n개를 퀸을 모두 놓은 것이 되기 때문에 전역변수 answer의 값을 1증가시켜주고 종료(return)해주면 된다. 그래서 bt(0)부터 시작해 x가 n이 될때까지 재귀 호출을 한다.
그리고 하나의 줄에서 값을 선택해야 하는데 이때는 y좌표만 확인해주면 된다.
따라서 y좌표는 0부터 n-1까지 반복하면서 이동가능한지 확인해준다.
이동 가능 여부는 cols, d1, d2 이 세가지 배열로 할 수 있다.
먼저 cols는 n의 크기를 가진 배열로 n번째 행에 퀸이 놓여져 있는지에 대한 bool 값을 저장한다.
d1은 양의 기울기를 가진 대각선 방향을 확인해 주는 배열이다.
n이 4인 경우 예를들어 (1,2) 위치를 선택하면 파란색에 있는 모든 위치을 선택하지 못하고, (2,2)위치를 선택하면 주황색의 모든 위치를 선택하지 못한다.
그렇다면 저 색상이 선택되었는지 아닌지만 체크하면 된다는 말이고 같은색으로 칠해져 있는 좌표의 특징을 찾아보면 x와 y좌표의 합이 같다는 특징을 찾을 수 있다.
즉 d1은 두 수의 합이 0인지, 1인지, 2인지 확인하는 배열로 0부터 2*n-2까지 필요하다. 그래서 초기 크기를 다음과 같이 설정한다.
const d1 = Array(2 * n - 1).fill(false);
d2도 동일하다 단 특징이 조금 다른게 x좌표와 y좌표의 합을 기준으로 배열을 나누는것이 아니라 x좌표와 y좌표의 차를 기준으로 배열을 나누면 된다.
두 수의 차는 -n+1 부터, n-1까지 총 2*n-1 크기를 가지는 배열을 만들어준다.
const d2 = Array(2 * n - 1).fill(false);이제 만들어진 세가지 배열로 이동 여부를 판별해주면 되는데 조건은 다음과 같다.
- 같은 열에 있거나 ->
cols[y] - 양의 기울기가 같거나 ->
x좌표와y좌표의 합이 같거나 =>d1[x + y] - 음이 기울기가 같거나 ->
x좌표와y좌표의 차가n-1여야 함 =>d2[x - y + n - 1]
위 세가지 조건중 하나만 만족해도 해당 좌표에는 퀸이 올 수 없으므로 continue로 다음 경우의 수를 확인해주면 된다.
만약 세가지 조건을 모두 만족하지 않아 퀸을 놓을 수 있다! 라면
다음과 같이 퀸을 놓고 백트래킹함수를 재귀호출 해주면 된다.
cols[y] = d1[x + y] = d2[x - y + n - 1] = true재귀호출을 한 뒤 다시 해당 좌표를 false로 바꿔놔서 다음 경우의 수도 확인할 수 있도록 해준다.
23년도에 처음 이 문제를 접했는데 풀이를 보고 이해조차 못했던 기억이 난다.... 지금은 한번에 풀어내지는 못해도 이해가 잘돼서 다행이다!
🔵 Ref
