[BOJ] 9663. N-queen

레몬커드요거트·2026년 4월 8일
알고리즘

코딩테스트준비

목록 보기
36/66
post-thumbnail

코드 팁

n*n 크기의 배열을 0으로 채우는 방법

자바스크립트에서는 Array.from()이나 fill() 메서드를 활용합니다.

  • Array.from() 사용 (권장):JavaScript
    const n = 5;
const matrix = Array.from({ length: n }, () => Array(n).fill(0));
  • map() 사용:JavaScript
    const n = 5;
const matrix = Array(n).fill().map(() => Array(n).fill(0));

코드리팩토링

// 00 01 02 03 04
// 10 11 12 13 14
// 20 21 22 23 24
// 30 31 32 33 34
// 40 41 42 43 44

AS-IS


function isSameLine(cx, cy, nx, ny) {
  // 같은 행인 경우 || 같은 열인 경우 || 대각선 같은 줄인 경우(\방향) || 대각선(/)방향
  if (cx === nx || cy === ny || cx - cy === nx - ny || cx + cy === nx + ny) {
    return true;
  } else false;
}

TO-BE

function isSameLine(cx, cy, nx, ny) {
  // 1. 같은 행 (Horizontal)
  // 2. 같은 열 (Vertical)
  // 3. 주 대각선 방향 (\ : i - j 가 일정)
  // 4. 반대 대각선 방향 (/ : i + j 가 일정)
  return cx === nx || cy === ny || cx - cy === nx - ny || cx + cy === nx + ny;
}

대각선 방향 판단

  1. 주 대각선과 평행한 대각선 (↘ 방향)

    01, 12, 23 혹은 10, 21, 32처럼 주 대각선과 평행하게 흐르는 선들입니다.

    • 특징: 행 인덱스(i)와 열 인덱스(j)의 차이가 일정합니다.
    • 판단 식: i−j=constanti - j = \text{constant}
      • 01, 12, 23: 모두 i−j=−1i - j = -1
      • 10, 21, 32: 모두 i−j=1i - j = 1
      • 주 대각선: i−j=0i - j = 0

  2. 반대 대각선과 평행한 대각선 (↙ 방향)

    01, 10 혹은 03, 12, 21, 30처럼 반대 대각선과 평행한 선들입니다.

    • 특징: 행 인덱스(ii)와 열 인덱스(jj)의 합이 일정합니다.
    • 판단 식: i+j=constanti + j = \text{constant}
      • 01, 10: 모두 i+j=1i + j = 1
      • 12, 21: 모두 i+j=3i + j = 3

잘못된 코드

const fs = require("fs");
const input = fs.readFileSync(
  process.platform === "linux" ? "/dev/stdin" : "input.txt",
);

// 같은 열에 2개 이상 배치X
// 같은 행에 2개 이상 배치X
// 같은 대각선 방향에 2개 이상 배치X

N = Number(input);
grid = Array.from({ length: N }, () => Array(N).fill(0));

function isSameLine(cx, cy, nx, ny) {
  // 1. 같은 행 (Horizontal)
  // 2. 같은 열 (Vertical)
  // 3. 주 대각선 방향 (\ : i - j 가 일정)
  // 4. 반대 대각선 방향 (/ : i + j 가 일정)
  return cx === nx || cy === ny || cx - cy === nx - ny || cx + cy === nx + ny;
}

// 같은 줄에 1개씩만 있어야함
// 1. 임의의 위치 말 배치(0->1)
// 2. 같은 줄에 있는 모든 셀 1로 변경
// 3. 1이 아닌 곳에 말 배치(0->1)
// 4. 같은 줄에 있는 곳 모든 셀 1로 변경 ... depth가 N가 될 때까지 반복
let cnt = 0;

function solve(grid, depth) {
  if (depth === N) {
    cnt += 1;
    return;
  }

  for (let j = 0; j < N; j++) {
    for (let i = 0; i < N; i++) {
      if (grid[j][i] === 0) {
        const temp_grid = grid.map((row) => [...row]);

        for (let r = 0; r < N; r++) {
          for (let c = 0; c < N; c++) {
            if (isSameLine(i, j, c, r)) {
              temp_grid[r][c] = 1;
            }
          }
        }
        solve(temp_grid, depth + 1);
      }
    }
  }
}

solve(grid, 0);
console.log(cnt);

시간 초과 인듯

const fs = require("fs");
const input = fs.readFileSync(
  process.platform === "linux" ? "/dev/stdin" : "input.txt",
);

// 같은 열에 2개 이상 배치X
// 같은 행에 2개 이상 배치X
// 같은 대각선 방향에 2개 이상 배치X

N = Number(input);
grid = Array.from({ length: N }, () => Array(N).fill(0));

function isSameLine(cx, cy, nx, ny) {
  // 1. 같은 행 (Horizontal)
  // 2. 같은 열 (Vertical)
  // 3. 주 대각선 방향 (\ : i - j 가 일정)
  // 4. 반대 대각선 방향 (/ : i + j 가 일정)
  return cx === nx || cy === ny || cx - cy === nx - ny || cx + cy === nx + ny;
}

// 1. 임의의 위치 말 배치(0->1)
// 2. 같은 줄에 있는 모든 셀 1로 변경
// 3. 1이 아닌 곳에 말 배치(0->1)
// 4. 같은 줄에 있는 곳 모든 셀 1로 변경 ... depth가 N가 될 때까지 반복
let cnt = 0;

function solve(current_grid, row) {
  // 한 행에 모두 퀸을 배치하면 됨
  if (row === N) {
    cnt += 1;
    return;
  }

  // 현재 행(row)에서 어느 열(col)에 둘 수 있는지 검사
  for (let col = 0; col < N; col++) {
    // 0인 자리에만 퀸을 놓을 수 있음
    if (current_grid[row][col] === 0) {
      const next_grid = grid.map((row) => [...row]);

      for (let r = 0; r < N; r++) {
        for (let c = 0; c < N; c++) {
          if (isSameLine(col, row, c, r)) {
            next_grid[r][c] = 1;
          }
        }

        // 다음 행으로 넘어가기
        solve(next_grid, row + 1);
      }
    }
  }
}

solve(grid, 0);
console.log(cnt);

아이디어

  1. 한 행에 하나의 퀸을 배치해야 한다.

    0번 행부터 N-1번 행까지 한 줄에 하나씩만 놓으면서 내려가면 훨씬 빠름

  2. 배열 전체를 매번 복사하지 않고, visited 배열을 쓰거나 재귀 호출 직후에 상태를 되돌리기

대각선 배열 만들기

1. 왜 diag2[row + col] 인가 ( / 방향 )

보드를 좌표 (row, col)로 보면: 같은 / 방향 대각선에 있는 좌표들은 row + col 값이 동일

예시 (N=5):

(0,4) → 0+4=4
(1,3) → 1+3=4
(2,2) → 2+2=4
(3,1) → 3+1=4
(4,0) → 4+0=4

즉, / 방향 대각선 = row + col이 같은 집합

diag2[row+col]

2. 왜 diag1[row - col + N] 인가 ( \ 방향 )

이번엔 \ 방향: 같은 대각선은 row - col 값이 동일합니다.

예시:

(0,0) → 0-0=0
(1,1) → 1-1=0
(2,2) → 2-2=0

또 다른 대각선:

(0,2) → 0-2=-2
(1,3) → 1-3=-2
(2,4) → 2-4=-2

즉, \ 방향 대각선 = row - col이 같은 집합

그런데 문제 발생 row - col 값은 음수가 나올 수 있음

(0,4) → -4

배열 인덱스는 음수를 못 쓰니까 보정 필요 → +N을 해준다

diag1[row-col+N]
범위: -(N-1) ~ (N-1)
→ +N 하면
1 ~ 2N-1

즉, 안전하게 배열 인덱스로 사용 가능

방향조건코드
세로col 같음col[col]
/row + col 같음diag2[row + col]
\row - col 같음diag1[row - col + N]

코드 결론

const fs = require("fs");
const input = fs.readFileSync(
  process.platform === "linux" ? "/dev/stdin" : "input.txt",
);

// 같은 열에 2개 이상 배치X
// 같은 행에 2개 이상 배치X
// 같은 대각선 방향에 2개 이상 배치X

N = Number(input);
grid = Array.from({ length: N }, () => Array(N).fill(0));

let cnt = 0;

const col = Array(N).fill(false);
const diag1 = Array(2 * N).fill(false); // row - col + N
const diag2 = Array(2 * N).fill(false); // row + col

function solve(row) {
  // 한 행에 모두 퀸을 배치하면 됨
  if (row === N) {
    cnt += 1;
    return;
  }

  // 현재 행(row)에서 어느 열(col)에 둘 수 있는지 검사
  for (let c = 0; c < N; c++) {
    if (col[c] || diag1[row - c + N] || diag2[row + c]) continue;

    col[c] = true;
    diag1[row - c + N] = true;
    diag2[row + c] = true;

    solve(row + 1);

    // 모두 초기화 해줘야함....
    col[c] = false;
    diag1[row - c + N] = false;
    diag2[row + c] = false;
  }
}

solve(0);
console.log(cnt);
profile
레몬커드요거트
비요뜨 최고~
이전 포스트

[BOJ] 14502. 연구소

다음 포스트

[BOJ] 1806. 부분합(javascript)

0개의 댓글