[node.js, 백준]9663 - N-Queen

목차

 문제

링크

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

문제

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

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

입력

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

 

출력

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

 

주저리

로직은 이해했으나 시간 초과가 일어나서 최적화하는데 애를먹었고 결국 최적화코드는 답을봐서 한번더 풀어야할 것같다.

 

Queen을 N x N칸에 N개 배치할때 핵심은 한 줄에 하나씩 퀸이 꼭들어가야하는점을 생각해야했다.(경우의 수 줄이기)

 

그리고 반복문으로 해결하였는데 하나의 퀸을 배치하면 그 공격 대상에 다른 퀸이있는지 체크를 해줘서 없다면 결국 다 배치하면 count를 늘리는식으로 해결하면된다.

 

풀이

 checkAttack : 공격 위치 확인 함수

• checkAttack(x, y): 주어진 위치 (x, y)에 퀸을 놓을 수 있는지 확인하는 함수입니다. 가로, 세로, 대각선을 검사하여 공격 가능한지 확인합니다.

 go : 백트래킹 함수

• go(index): 퀸을 배치하기 위한 백트래킹 함수입니다. index는 현재 배치 중인 퀸의 행을 나타냅니다. 각 열에 대해 퀸을 놓을 수 있는지 확인하고, 가능하면 퀸을 배치하고 다음 행으로 이동합니다.

 solution 함수

• solution(): 백트래킹 함수를 호출하여 퀸을 배치하고 가능한 모든 배치 방법의 수를 출력합니다.

 코드

// N-Queen
var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString();

let real = input.trim().split("\n");
let [k, ...rests] = real;
let N = Number(k)
let checksArray = Array.from({ length: N }, () => Array.from({ length: N }).fill(0));

function checkAttack(x, y) {
    // 가로줄 확인
    for (let i = 0; i < N; i++) {
        if (checksArray[y][i] === 1) {
            return false;
        }
    }

    // 세로줄 확인
    for (let j = 0; j < N; j++) {
        if (checksArray[j][x] === 1) {
            return false;
        }
    }

    // 좌측 상단
    let leftUpX = x;
    let leftUpY = y;
    while (leftUpX > 0 && leftUpY > 0) {
        leftUpX -= 1;
        leftUpY -= 1;
        if (checksArray[leftUpY][leftUpX] === 1) {
            return false;
        }

    }

    // 좌측 하단
    let leftDownX = x;
    let leftDownY = y;
    while (leftDownX > 0 && leftDownY < N - 1) {
        leftDownX -= 1;
        leftDownY += 1;
        if (checksArray[leftDownY][leftDownX] === 1) {
            return false;
        }

    }

    // 우측 상단
    let rightX = x;
    let rightY = y;
    while (rightX < N && rightY > 0) {
        rightX += 1;
        rightY -= 1;
        if (checksArray[rightY][rightX] === 1) {
            return false;
        }

    }

    // 우측 하단
    let rightDownX = x;
    let rightDownY = y;
    while (rightDownX < N - 1 && rightDownY < N - 1) {
        rightDownX += 1;
        rightDownY += 1;
        if (checksArray[rightDownY][rightDownX] === 1) {
            return false;
        }

    }


    return true;
}

let count = 0;
function go(index) {
    if (index >= N) {
        // console.log('정답일때', index, { checksArray })
        count++;
        return;
    }
    for (let i = 0; i < N; i++) {
        if (checkAttack(i, index)) {
            checksArray[index][i] = 1;
            go(index + 1)
            checksArray[index][i] = 0;
        }
    }


}


async function solution() {
    go(0, []);

    console.log(count);
    // go(0, []);
}
solution();