백준 9663: N-Queen - javascript(백트래킹) //좋은 문제

문제 출처 

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

 

정답 풀이 

N-Queen 문제에서 체스 큐칙은 아래와 같다. 

- 퀸은 한행, 한 열에 하나씩만 놓을 수 있다. 

- 서로 같은 대각선상에 있으면 안된다. 

 

아래 그림에서 빨간 부분은 피해서 다음 퀸을 놓아야 한다는 뜻 !

 

가로나 세로는 피할 수 있겠고, 

대각선은 어떻게 피할 수 있을까? 

 

먼저 대각선 방향은 두개를 생각해줘야 한다. 

- 오른쪽 대각선 밑으로. 

- 왼쪽 대각선 밑으로. 

 

먼저 왼쪽 대각선 밑 방향 좌표들의 공통점은?

=> x좌표와 y좌표의 합이 같다 !!! 

 

n=4일 때 x좌표 + y좌표의 합의 

- 최솟값은 0이고  

- 최댓값은 n*2-2 이다. 

이를 배열로 표현하면 

let diag1 = new Array(n*2-1)로 하면되겠다. (0~6을 표현하기 위해선 7크기의 배열이 필요하므로) 

 

만약 diag1[2] = true 라면 해당 대각선에 퀸이 놓인 것이니, 그 대각선엔 새로운 퀸을 놓을 수 없다. 

 

다음으로 오른쪽 대각선 밑 방향 좌표들의 공통점은?

=> x-y의 값이 같다는 점 !! 

 

 

그런데 유의할 점이 있다. 값을 빼주는 것이다 보니, 이건 음수가 발생할 수 있다. 

0-1 은 = -1

1-2는 = -1 

2-3은 = -1

 

 

이렇게 x-y를 해줬을 때 최댓값은 얼마일까? 

x가 제일 크고, y가 제일 작을 때 

=> 3이 된다. 

 

최솟값은 얼마일까? 

=> -3이 된다. 

 

이를 배열로 어떻게 표현해줄까?

아래와 같이 배열을 만들어주면 된다. 

 

그런데 배열은 음수 인덱스를 갖지 않는다. 

어떻게 표현해줄까? 

아래와 같이 오른쪽에 붙여보자 ! 

 

 

 

x-y = -1 이였던 

즉, -1인덱스로 표현해야 했던 경우를 

x-y+n+1 로 표현할 수 있겠다. 

즉, 4인덱스로 표현하자 ! 

 

자, 그럼 같은 대각선에 놓여져있는지 확인하는 법은 알겠으니, 

문제를 어떻게 풀지 알아보자. 

이 부분은 이해하기 매우 쉽다 ! 

 

먼저, 세로를 L로 둔다. 

그래서 dfs(L) 0부터 시작해서 

종료조건은 L === n이 될 때이다. (n이 8일때 가정) 

각 열에 퀸을 하나씩밖에 못두니까 +1 씩 올리면 된다. 

 

만약 L = 0일 때 퀸을 아래와 같이 두었다면, 

L=1일 때 반복문을 통해서 전체를 다 탐색해야 한다. 둘 수 있는 곳에 다 둘 것임. 

 

L은 각각 0과 1로 당연히 다르므로(세로) 

가로와 대각선만 다른지 확인해주고, 

다를때 퀸을 두면 된다. 

이는 조건식으로 표현하자 !

 

그럼 모든 이해는 끝났다. 코드로 작성하자. 

 

정답 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
const n = Number(input.shift())

function solution(n){
 let answer = 0;
 const row_checked = new Array(n).fill(false);  //가로 중복 체크 배열
 const diag1 = new Array(2 * n - 1).fill(false); //왼쪽 대각선 체크 배열
 const diag2 = new Array(2 * n - 1).fill(false); //오른쪽 대각선 체크 배열
    function dfs(L){
     if(L === n){ //퀸을 다 두었을 때 
         answer++; 
         return; 
     }else{
       for(let j=0; j<n; j++){ //가로 전체 탐색 
         if(!row_checked[j] && !diag1[L+j] && !diag2[L-j+n+1]){ //가로, 대각선 중복 체크 조건 만족할 때

           row_checked[j] = true; 
           diag1[L+ j] = true; 
           diag2[L-j+n+1] = true; 
           
           dfs(L+1); //다음 세로 줄로 가기. 
           
           row_checked[j] = false; 
           diag1[L+ j] = false
           diag2[L-j+n+1] = false
         }
       }
     }
 }
    dfs(0)
    return answer; 
}

console.log(solution(n))