[JS] 프로그래머스_Level 2_N-Queen

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12952

프로그래머스

 

 

풀이

체스의 퀸이 움직일 수 있는 칸의 유형을 보자.

퀸이 움직일 수 있는 범위는 4방향의 직선과 4방향의 대각선을 움직일 수 있다. 그렇기 때문에 N-Queen 문제에서는 모든 퀸의 위치에서의 8방향에서 또다른 퀸이 존재하지 않는 경우의 수를 구해야 한다.

 

위의 설명을 조금 생각해 본다면 한 줄에 하나의 퀸을 놓을 수 있다.(직선에 중복되는 퀸이 있으면 안된다)

이 조건을 만족하기 위해서는 가로줄에 하나만 두기 위해 퀸의 위치를 저장하는 배열을 세로줄의 길이만큼 선언한 뒤 ([-1, -1 , -1 , -1 ]) 각 요소에 세로의 위치를 저장한다([1, 3, 0, 2]).

 

이렇게 직선(가로 세로)상 하나의 퀸만 존재하는 경우를 찾았으며, 이제는 대각선의 경우를 생각해야한다. 대각선의 검증 유도식은 다음과 같다. 두개의 퀸이 대각선에 있는 경우 각 x좌표의 차와 y좌표의 차가 같은 경우 퀸이 대각선에 존재하는 것을 알 수 있다.

 

그렇다면 직선과 대각선에 있는 퀸을 검출할 수 있는 로직을 전부 구했다. 이제 접근법을 결정해야하는데, 이러한 조합의 경우를 구하는 문제는 DFS로 접근하려한다.

코드

function solution(n) {
  let answer = 0;
  const arr = Array.from({ length: n }, () => -1);
    
  const valify = (arr, x, y) => {
    for (let i = 0; i < x; i++) {
      if (Math.abs(x - i) === Math.abs(y - arr[i]) || arr[i] === y) return false;
    }
    return true;
  }
    
  const dfs = (arr, depth) => {
    if (depth === n) {
      answer++;
      return;
    }
    const temp = [...arr];
        
    for (let i = 0; i < n; i++) {
      if (valify(temp, depth, i)) {
        temp[depth] = i;
        dfs(temp, depth + 1);
      }
    }
  }
  dfs(arr, 0);
  return answer;
}