[프로그래머스] N-Queen (Lv 2) - javascript

문제

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.
 

 

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

• 제한사항
  • 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
  • n은 12이하의 자연수 입니다.

 

🔑 Backtracking 알고리즘 (dfs)

backtraking은 dfs 알고리즘의 방식 중 하나이다,
깊이 우선 탐색으로 조사를 이어가다가, 조건에 맞지 않으면 바로 상위로 빠져나오는 방식이다.
하위 경우의 수는 더 조사하지 않는다. 그러므로 모든 경우의 수를 조사하는 것보다 효율성과 속도가 빠르다.
 
자세한 설명

 

📝 구현

해당 문제는 backtracking 알고리즘을 이용하여 구현하면 된다.

하지만 문제를 풀수록 알고리즘도 중요하지만, 그것은 거들 뿐이라는 생각이 든다.

진짜 문제는 추상화의 '구현'이다.

데이터를 효율적으로 저장하는 구조를 만들고 재귀나 순회로 답을 도출하는 과정에서 헤매게 된다.

특히 재귀는 귀납적 사고를 필요로 하기 때문에 훈련이 필요하다.
 

퀸을 배치하기 위한 조건

1. (가로, 세로 공격 불가하도록) 각 행에 하나씩, 모두 다른 행에 배치
2. (대각선 공격 불가하도록) 이미 존재하는 퀸(행, 열)의 (행+n, 열+n) 에는 배치X
    
   

   

   
   X(0,0) 에서 대각선에 놓인 1(1,1), 2(2,2), 3(3,3)은 모두 X의 행, 열로부터 같은 거리에 있다(0+n,0+n)

구현 과정

1. 배열 board 생성: 퀸의 열을 저장할 1차원 배열 (인덱스 = 퀸의 행, 값 = 퀸의 열)
2. 변수 answer 생성: 경우의 수 카운트할 변수
3. for문: 행 순회
   3-1. 첫번째 퀸의 열을 board에 저장
   3-2. dfs함수 실행
4. answer 반환

• dfs 함수 (재귀 함수)

  1. (종료 조건) 마지막 행까지 퀸이 추가됐다면 => 경우의 수 추가 (answer++)
  2. for문: 다음 행의 열 순회 (배치 가능한지 순회해서 알아냄)
     2-1. board[다음 행]에 열 추가
     2-2. (조건) 해당 열이 추가 가능하다면 (isValid 함수) => 다음 행으로 dfs 함수 호출

• isValid 함수 (board, row 인자로 받음)
  board의 모든 값을 순회

  1. 열이 같으면 => false
  2. 행, 열로부터 같은 거리만큼 떨어져 있으면 => false
  3. 둘 다 아니라면 => true
      

코드

function solution(n) {

    let answer = 0;

    for(let i = 1; i <= n; i++) {
        let board = new Array(n+1).fill(0);
        board[1] = i;
        dfs(board, 1);
    }
    return answer;

    function dfs(board, row) {

        if(row === n) answer++;

        else {
            for(let j = 1; j <= n; j++) {
                board[row+1] = j;
                if(isValid(board, row+1)) dfs(board, row+1);
            }
        }
    }

    function isValid(board, row) {

        for(let k = 1; k < row; k++) {
            if(board[k] === board[row]) return false;
            if(Math.abs(k-row) === Math.abs(board[k]-board[row])) return false;
        }
        return true;
    }
}

 

• 정확도 테스트 결과
  
   

---

참고

programmers.co.kr/learn/courses/30
velog.io/@longroadhome
velog.io/@jeongin/Javascript
바킹독님의 재귀 강의