프로그래머스 코딩테스트 (4) - N-Queen

📖 문제 설명

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

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

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

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

👨🏻‍💻 코드와 분석

function solution(n) {
  let answer = 0;
  const dfs = (board, row) => {
    // 열과 선언된 수가 같으면 답을 추가한다.
    // 재귀함수를 돌면서 행이 n의 값까지 오게 된다면 모든 조건을 만족한것이다.
    if (row === n) answer++;
    else {
      for (let i = 1; i <= n; i++) {
        // 각 행의 열의 위치를 옮겨준다.
        board[row + 1] = i;
        // 각 행의 열의 위치를 옮기면서 조건을 만족할 경우 다음행으로 이동시키기 위해
        // 재귀함수를 호출한다.
        // 재귀함수가 종료되고 그 전에 호출되었던 함수가 다시 실행되는것은 분기점이다.
        if (isValid(board, row + 1)) dfs(board, row + 1);
      }
    }
  };

  // 백트레킹스 알고리즘 제한사항에 해당할 경우 해당 브렌치를 쳐내서 부담을 줄임
  const isValid = (board, row) => {
    //
    for (let i = 1; i < row; i++) {
      // 세로가 겹치는지 확인
      // 각 행의 열이 같다면 취소임.
      // 대각선이 겹치는지 확인
      // 열과 열의 차이와 행과 행의 차이가 같으면 같은 대각선상에 있음.
      if (
        board[i] === board[row] ||
        Math.abs(board[i] - board[row]) === Math.abs(i - row)
      )
        return false;
    }
    // 조건을 만족할 경우 true를 리턴함.
    return true;
  };

  for (let i = 1; i <= n; i++) {
    // 1차원 배열로 전달받은 n보다 1큰 배열을 생성한다.
    // board는 1차원이기 때문에 곧 각 인덱스에 위치한 숫자는 퀸이 위치하는 열을 의미한다.
    // 그렇기 때문에 각 행에는 한개의 퀸만 위치할 수 있다.
    const board = new Array(n + 1).fill(0);
    // 첫번째 행의 열 값은 순회시킨다.
    board[1] = i;
    // 깊이 우선 탐색 알고리즘을 호출한다.
    dfs(board, 1);
  }

  return answer;
}

console.log(solution(4));

😀 마무리

사실 너무 어려워서 해결하지 못했다.. 레벨 1에서 2로 올라왔을 뿐인데, 알고리즘을 적용해야하는 코드가 나올 줄은 몰랐고, 알고리즘도 처음 접해봐서 이해하는데도 오래 걸렸다. 알고리즘을 통해 지금까지 해왔던 코드들도 뭔가 개선을 할 수 있겠다라는 생각이 든다.
또 이 코드를 이해하면서 배웠던 점도 많아서 따로 로깅을 해놓았다!
알고리즘 - 백트레킹