백준 9663: N-Queen

Song-Minhyung·2022년 5월 31일

Problem Solving

목록 보기

5/50

문제

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

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

Try 1

풀이방법

const find = (row: number, col: number, visited: number[][]) => {
    if (visited[row][col] === 1 || visited[row][col] === 2) {
        // cnt++;
        return;
    }
    visited[row][col] = 1;

    for (let i=0; i<N; i++) {
        for (let j=0; j<N; j++) {
            for (let k=0; k<pos.length; k++) {
                const x = pos[k][0] + i;
                const y = pos[k][1] + j;

                // 배열의 영역을 벗어나지 않을 경우
                // 퀸의 이동 범위를 모두 true로 체크해줌
                if ( x >= 0 && x < N 
                    && y >= 0 && y < N
                ) {
                    find( y, x, visited);
                }
            }
        }
    }
}

재귀함수 안에서 for문을 돌려 모든 경우의 수에 접근한다.
queen을 놓을수 없는곳은 visited[i][j] = true로 표시한다.

Catch 1

해당 퀸이 도달할 수 없는 장소까지 true로 표기한다. 다른방법이 필요하다

Try 2

풀이방법

const N = +input();
const board = Array.from(
    {length: N}, () => 
        Array.from({length: N}, () => 0)
);
let cnt = 0;

const find = (beforeCol: number, canPutQueen: boolean[]) => {
    if (canPutQueen.every(val => val === false)) cnt++;

    for (let i=0; i<N; i++) {
        for (let j=0; j<N; j++) {
            // 만약 이전 row의 -1, 1, +1이 아닐 때
            // && 해당 col이 queen을 놓을 수 있는 위치인 경우
            if ( !(j >= beforeCol - 1 && j <= beforeCol + 1) && (canPutQueen[j] )
            ) {
                canPutQueen[j] = false;
                find( j, canPutQueen);
            }
        }
    }
}

for (let i = 0; i < N-1; i++) {
    const canPutQueen = Array(N).fill(true);
    for (let j=0; j<N; j++) {
        canPutQueen[j] = false;
        find(j, canPutQueen);
    }
}
console.log(cnt);

바깥의 for문에서 모든 경우의 수에대해 재귀함수를 돌렸음.
어떤 어떤 열에 퀸이 놓인다면 해당 열에는 퀸이 못놓이는 방식으로 접근함
0행의경우 마지막의 행도 퀸을 못놓음, 반대의 경우도 마찬가지임

Catch 2

대각선의 경우도 어디에 놓으면 안되는지 알 수 없음.

Finally 2

대각선은 어떻게 해결하면 좋을까?
1. i, j를 더하니 왼쪽아래 -> 오른쪽 위로 향하는건 전부 같은값을 보임
2. i, j를 빼니 왼쪽위 -> 오른쪽 아래로 향하는건 전부 같은 값을 보임
  1. 하지만 음수도 있음.
  2. 음수를 대비해서 배열을 N의 2배로 늘리면 될것같음

Try 3

풀이방법

const N = +input();
// 가로로 놓을수 있는지 확인
const canPutCol = Array(N).fill(true);
// 왼쪽아래 -> 오른쪽 위 대각선 놓을 수 있는지 확인
const rightUp = Array(N*2).fill(true);
// 왼쪽위 -> 오른쪽 아래 대각선 놓을 수 있는지 확인
const rightDown = Array(N*2).fill(true);
let cnt = 0;

const find = (row: number) => {
    if (row === N) {
        cnt ++;
        return;
    }

    for (let col=0; col<N; col++) {
        if ( canPutCol[col]
            && rightUp[row - col + N]
            && rightDown[row+col]
        ){
            canPutCol[col] = false;
            rightUp[row - col + N] = false;
            rightDown[row + col] = false;

            find( row + 1);

            canPutCol[col] = true;
            rightUp[row - col + N] = true;
            rightDown[row + col] = true;
        }
    }
}
find(0);
console.log(cnt);

풀이 방법을 계속 바꾼 끝에 드디어 성공했다.
기존에 for문을 재귀 바깥에서 한번, 안에서 한번 중복돼서 계속 돌리는게 아니라고 생각했다.
앞서 푼 N, M 문제를 생각해보니 굳이 밖에서 돌릴 필요가 없었다.
어차피 N개의 줄을 내려가면서 돌아갈거니까!!!

가로줄에서 어디에 놓으면 안되는지 검사하는건 간단했다.
그냥 배열 만들고서 해당 줄에 놓으면 못놓게 했다.
대각선 체크가 문제였다. 생각해보고 시도해본건 아래와 같다
1. 2차원 배열을 만들어서 체크한다.
  -> 시간이 너무 많이든다. 바로 넘어간다.
2. 가로, 세로 체크하는 변수를 활용해서 체크한다.
  -> 2차원 배열을 비교하는 시간과 비슷한 시간이 든다.
3. 대각선만 따로 계산해본다.
  -> 대각선의 i,j를 활용해 덧셈, 뺄셈을 하면 같은값이 나온다.
  -> 여기서 나온값은 8개인데, 한개의 값으로 봐도 무방하다.
  -> 이를 활용해 대각선위, 대각선아래를 계산하는 변수를 두개 만든다.
  -> 음수의 경우도 있으므로 배열의 길이에 2를 곱해준다.
재귀를 들어갈 때 대각선 변수를 false로 바꾸고 재귀를 나올 때 되돌려준다.