프로그래머스 :: N-Queen, Javascript

😺 풀어 볼 문제

프로그래머스 :: N-Queen
코딩테스트 준비하면서 세 번 정도 풀었던거 같은데, 왜 매번 풀 때마다 새로운지 모르겠다. 아는게 아니라 익숙했기 때문에 그런거 같다. 이번 기회에 확실하게 알기위해 정리 해 놓으려고 한다.

간단한 풀이 설명

대표적인 백트래킹 문제이다.
재귀를 통해서, 조건에 맞으면 퀸을 놓고 조건에 맞지 않으면 다음 것으로 탐색을 진행하면 된다. 말은 쉽다
조금 더 자세히 설명하자면, 퀸은 가로, 세로, 대각선 방향으로 움직일 수 있다.
그러니까, 어차피 가로에는 하나 밖에 놓을 수 없으니, 놓을 수 있는 자리면 놓고, 다음 row로 이동해서 놓을 위치를 탐색하는것이 목표이다.

아래 그림처럼, 첫째 줄에 두번째 칸에 놓은 경우 빨간색으로 칠한곳은 다른 퀸을 놓을 수 없다.

4X4 사이즈의 체스판에서, 우리는 [1,3,0,2]와 같이 표현할 건데, 이는 첫번째 줄에 두번째 칸에 첫 퀸이 놓여있고, 두번째 줄에 마지막 칸에 두번째 퀸이 놓인다는 뜻이다. 이 값과 인덱스를 이용해서 놓을 수 있는지 없는지 판단할 것이다.

부분 코드

먼저, 체스판의 크기에 맞게 배열을 선언 해 준다.

let queen = Array.from({length: n}, () => 0);

이후, 재귀 탐색을 할 dfs 함수를 작성 할 것이다.

    function dfs(row){
    // row의 값이 n이랑 같은 경우 모든 줄에 퀸을 다 놓았다는 뜻이므로 1을 더해준다.
        if( n === row){
            answer += 1
        }

    // 위 조건이 만족하지 않을 경우
    // row 번째 줄부터 0 번째~n - 1 번째 칸까지 탐색을 진행한다. 
        for(let col = 0 ; col < n ; col++){
         // 먼저 row번째 줄의 col번째 칸에 놓아보자. 
            queen[row] = col
              // 못 놓는다고 판별이 되는 경우 반복문을 빠져나와야 하므로, 플레그를 세워둔다.
            let checker = true

            //이제 제일 첫 줄부터 row 줄까지 돌면서, 그 col칸에 놓아도 되는지 판별한다. 
            for( let i = 0 ; i < row ; i++){
                //세로줄에 퀸이 있는지 판단하는 조건문이다.
                  //queen[row]는 현재 col값이고, queen[i]의 값은 i번째 줄의 col값이므로
                // 같은 경우는 같은 세로 줄에 놓여있다는 의미이다.
                  // 때문에 플레그를 끈 뒤, 반복문을 탈출해준다.
                if(queen[row] === queen[i]){
                    checker = false
                    break
                }
                  // 대각선에 퀸이 있는지 판단하는 조건문이다.
                  // 현재 놓으려는 곳이 i번째 줄의 퀸과의 row의 차와 col의 차이가 같은 경우 대각선이라고 판단 할 수 있다.
                  // 같은 경우 플레그를 끈 뒤, 반복문을 탈출해준다.
                if(Math.abs(queen[row] - queen[i]) === Math.abs(i-row)){
                    checker = false
                    break
                }
            }
              // break를 통해 빠져나오지 않았다면, 다음 줄로 넘어가서 탐색을 진행해준다.
            if(checker) dfs(row+1);
        }

마지막으로, 첫 줄은 놓은 뒤에 재귀를 돌려야 정상적으로 작동하기 때문에 해당 코드를 작성한다.

  for (let i =0  ; i < n ; i++){
        queen[0] = i
        dfs(1)
   }

전체 코드

function solution(n) {

    let answer = 0
    let queen = Array.from({length: n}, () => 0);

    for (let i =0  ; i < n ; i++){
        queen[0] = i
        dfs(1)
    }

    function dfs(row){
        if( n === row){
            answer += 1
        }
        for(let col = 0 ; col < n ; col++){
            queen[row] = col
            let checker = true
            for( let i = 0 ; i < row ; i++){
                if(queen[row] === queen[i]){
                    checker = false
                    break
                }
                if(Math.abs(queen[row] - queen[i]) === Math.abs(i-row)){
                    checker = false
                    break
                }
            }
            if(checker) dfs(row+1);
        }
    }

    return answer;
}

코드를 외워서 익숙해지기보다, 어떻게 돌아가는지 완벽하게 이해하는 것이 중요하다.