[프로그래머스][JavaScript]N-Queen

문제 

N-Queen

프로그래머스

2차원 배열 코드 

function solution(n) {
    let answer = 0;

    // 체스판을 2차원 배열로 초기화
    const board = Array.from( Array(n), () => Array(n).fill(0));

    // 해당 위치에 퀸을 놓을 수 있는지 확인하는 함수
    function isSafe(row, col) {
        // 같은 열을 확인
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 1) {
                return false;
            }
        }

        // 왼쪽 위 대각선 확인
        for (let i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] === 1) {
                return false;
            }
        }

        // 오른쪽 위 대각선 확인
        for (let i = row, j = col; i >= 0 && j < n; i--, j++) {
            if (board[i][j] === 1) {
                return false;
            }
        }

        return true;
    }

    // 퀸을 배치하는 함수 (백트래킹)
    function placeQueens(row) {
        if (row === n) {
            // 모든 퀸을 성공적으로 배치한 경우
            answer++;
            return;
        }

        for (let col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                // 현재 위치에 퀸을 놓을 수 있다면
                board[row][col] = 1; // 퀸을 놓고
                placeQueens(row + 1); // 다음 행으로 이동
                board[row][col] = 0; // 백트래킹: 다른 경우를 위해 퀸을 제거
            }
        }
    }

    // 첫 번째 행부터 시작
    placeQueens(0);

    return answer;
}

2차원 배열을 사용해 구현한 코드이다. 행을 기준으로 열, 대각선을 각각 검사하게 되는데

1차원 배열로도 구현이 가능하다.

1차원 배열을 통해 적은 비용으로 가지치기를 해보자. 

 

• 배열의 index: 행의 위치, 해당 index의 value : 열의 위치 
• index 하나에 여러 value를 둘 수 없다. -> 행 가지치기
• index가 같다면 둘 수 없다. -> 열 가지치기
• 행과 열에 대한 차가 같다면 대각선에 있다는 것이다. -> 대각선 가지치기 

 

1차원 배열 코드 

function check(queen, row) {
  // 이전까지 두었던 퀸의 위치를 확인
  for (let i = 0; i < row; i += 1) {
      // 행의 위치와 대각선의 위치를 체크
      if (queen[i] === queen[row] || Math.abs(queen[i] - queen[row]) === row - i) {
          return false; // 둘 수 없다면 false
      }
  }
  
  return true; // 모두 통과되면 true
}

function search(queen, row) {
  const n = queen.length;
  let count = 0;
  
  if (n === row) { // 체스판 끝에 도달했을때가 재귀의 탈출 조건
      return 1;
  }
  
  for (let col = 0; col < n; col += 1) { // 0부터 n까지 열을 돌면 둘 수 있다.
      queen[row] = col; // 우선 퀸을 둔다
      if (check(queen, row)) { // 퀸을 둘 수 있다면
          count += search(queen, row + 1); // 다음 행으로 이동
      }
  }
  
  return count;
}

function solution(n) {
  // 미리 n개 만큼의 배열을 초기화,0번 행부터 시작
  return search(Array.from({ length: n }, () => 0), 0);
}

 

 

 

✅check point!

이중 배열 선언하기	arr = Array.from( Array(n), () => Array(n).fill(0)); arr = Array.from({ length: n }, () => Array(n).fill(0))
Math.abs()	절댓값 반환

 

💡idea 요약

백트래킹	모든 경우의 수를 탐색하는 알고리즘 가지치기 : 탐색이 불필요한 곳은 미리 막는다.  ex)DFS,BFS
문제 속 가지치기 조건	퀸을 둔 행은 가지치기 한다. 퀸을 둔 열은 가지치기 한다. 퀸을 둔 대각선 왼쪽, 오른쪽은 가지치기 한다.
1차원 배열 구현	최소한 의 비용으로 가지치기 가능  배열의 index: 행의 위치, 해당 index의 value : 열의 위치  index 하나에 여러 value를 둘수 없다. -> 행 가지치기 index가 같다면 둘수 없다. -> 열 가지치기 행과 열에 대한 차가 같다면 대각선에 있다는 것이다. -> 대각선 가지치기