[프로그래머스] LV.3 N-Queen (JS)

문제

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

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

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

제한

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

입출력 예시

n	result
4	2

풀이

backtraking을 대표하는 N-Queen 문제이다. 위키백과에도 등재되어 있을만큼 유명한 문제이다. backtracking을 간단히 설명하면 DFS 같은 방식으로 탐색을 진행하며 나아갈 때 다음에 도달하는 노드로 인해 정답이 될 수 없는 경우가 발생하면 해당 라인의 탐색은 전부 포기하고 돌아오는 기법을 말한다. 따라서 우리는 해당 문제를 기본적으로 DFS + Backtracking 으로 풀이할 것이다.

먼저 퀸의 공격범위를 알아야 한다. 제한사항에 따르면 퀸의 이동범위는 가로, 세로 그리고 대각선이다. (체스를 모르는 내겐 정말이지 사기적인 범위이다) 2차원 배열을 두고 첫칸부터 퀸을 하나씩 배치하면서 다음 칸에 퀸을 추가적으로 배치할 수 있는지 DFS 알고리즘을 활용하여 구현할 수 있을 것 같은 기분이 든다.

N-Queen은 워낙 유명한 문제이기 때문에 결론부터 말하자면 굳이 2차원 배열을 사용하여 풀이하지 않아도 문제없다. 2차원 배열을 체스판으로 생각했을 때 첫번째 라인에 퀸이 위치하게 되면, 어차피 해당 라인의 가로, 세로줄 전체에는 어떠한 퀸도 위치할 수 없다는 것을 알 수 있다. 따라서 이는 1차원 배열로도 접근할 수 있다. 1차원 배열의 index를 체스판의 가로라인으로 보고 해당 index에 직접 넣어줄 원소값을 체스판의 세로라인으로 생각할 수 있다. (반대의 경우도 가능하겠다. 이 경우 밑에서 구현할 로직의 순서만 조금 변경해주면 된다.)

예를 들어 [2, 4, 1, 3]이라는 배열이 있었다면 다음과 같이 해석하는 것이다.

1. 체스판[0][1] 위치에 퀸 한개 배치
2. 체스판[1][3] 위치에 퀸 한개 배치
3. 체스판[2][0] 위치에 퀸 한개 배치
4. 체스판[3][2] 위치에 퀸 한개 배치

따라서 2차원 배열을 1차원 배열로만 표현할 수 있다. N 크기의 1차원 배열을 완성할 수 있다면 이는 체스판에 N개의 퀸을 배치가능하다는 것과 동일하다.

그렇다면 이제 DFS 함수를 구현해보자. 먼저 n+1 크기의 1차원 배열 board를 만들어주자. n+1인 이유는 계산상의 편의를 위해 index가 0일때는 비워두고 사용하고자 하는 의도이다. 이 부분에 대해 따로 계산을 해줄거라면 굳이 n+1일 필요는 없다. board 배열의 길이가 n+1 이라면 board[1]이 항상 체스판의 시작위치가 된다. 해당 위치에 어떤 값을 넣어주냐에 따라 몇번째 라인에 퀸이 위치하느냐의 뜻이 될 것이다. 따라서 우리는 해당 칸에 모두 한번씩 퀸을 배치해줄 것이다. 그리고 DFS 탐색을 통해 해당 칸에 퀸이 위치했을 시 다음 칸에 위치할 수 있는 퀸의 위치를 먼저 검사하고 배치하는 식으로 나아갈 것이다. 따라서 다음과 같은 형태로 dfs 함수가 반복 호출될 것이다.

for(let i = 1; i <= n; i+) {
  const board = new Array(n+1).fill(0);
  board[1] = i;	// 체스판의 첫번째 세로라인 중 i칸에 퀸을 배치
  dfs(board, 1); // 배치가 완료된 체스판과 현재 세로라인인 1을 dfs 함수에 전달
}

dfs 함수는 재귀적으로 구현한다. 방법의 수를 어떻게 계산할지 먼저 생각해보면 위 반복문에서 전달받는 row 값이 문제의 n과 동일해지는 순간 모든 체스판까지 훑어보고 배치를 완료한 것이 되기 때문에 이 경우에 정답을 1씩 증가시킬 것이다. 그 외의 경우엔 전달받은 row+1 위치에서 위 반복문과 똑같이 퀸을 배치할 것이다. 다만 이때는 다음 라인으로 바로 넘어가기 전에 그 위치에 퀸을 배치해도 될 지 사전에 검사가 필요하다. 즉 앞에서 언급했던 것 처럼 다음에 나아가는 경우의 수가 정답이 될 수 없는 경우로 빠지는지 미리 검사하여 가지치기를 해주는 것이다. 이를 구현하면 다음과 같다. 하나 유의할 점은 일반적인 backtracking 에서는 해당 값을 방문하고 다음으로 나아가지 못하면 이 값은 다시 미방문 처리로 바꿔주어야 하는데 해당 문제에서는 별도로 이러한 처리를 굳이 하지 않아도 상관없다. 1차원 배열로 매번 값을 덮어쓰기 때문이 첫 번째 이유이고, 어차피 정답은 최종 라인까지 도달해야 하나씩 카운트되기 때문에 매번 초기화 할 필요가 없는 것이다. 물론 값을 다시 돌려놓는 식으로 구현해도 상관은 없다.

const dfs = (board, row) => {
  if(n === row) answer++;
  else {
    for(let i = 1; i <= n; i++) {
      board[row+1] = i;	// 다음 라인에 퀸을 배치하고
      // isValid 라는 함수를 통해 해당 위치 퀸이 유효한지 검사
      // 유효하다면 다음위치 계속 탐색
      if(isValid(board, row+1)) dfs(board, row+1);
      
      // 필요하다면 여기서 board[row+1] = 0 으로 
      // 다음 backtraking을 위한 처리가 가능하다.
      // 하지만 위에서 언급했듯 우린 배열을 1차원으로 최적화하기에
      // 이 과정이 필수는 아니다.
    }
  }
}

그렇다면 해당 위치의 배치한 퀸의 자리가 유효한지를 따로 검사해줄 함수를 따로 구현해보자. 현재 진행된 위치의 row 까지 반복문을 돌면서 해당 위치의 퀸의 자리가 유효한지 검사할 것이다. 먼저 동일한 가로 및 세로라인에는 퀸이 위치할 수 없다. 따라서 board[i] === board[row] 가 성립한다면 이는 동일 라인에 위치하고 있는 것이기 때문에 false를 반환하도록 한다.

그리고 대각선 상에 있는지상에 있는지 체크해주어야 한다. 현재 1차원 배열로 압축해서 표현하고 있는데 대각선의 관계를 어떻게 체크해주어야 할까? 2차원 배열일때를 먼저 생각해보자.

다음처럼 두 개의 X가 현재 배치되어 있는 상태라고 하자. 각각 빨간 배경과 파란 배경이 X를 기준으로 대각선으로 배치되어 있는 상태가 될 것이다. 이때 대각선 라인에 있는 좌표를 보면, 2차원 배열의 열(Column)과 행(Row)의 차이가 일정한 것을 알 수 있다. 예를 들어 파란색 배경의 X 좌표는 (열, 행)으로 표시하면 (1, 2) 이다. 반대로 (행, 열)로 표시하면 (2, 1)이다. 이 둘의 차이는 1로 일정하다. 그리고 파란색 라인에 있는 모든 대각선 라인 역시 둘 사이의 차이가 1로 일정한 것을 알 수 있다. 따라서 우리는 대각선의 경로를 열의 차와 행의 차가 동일한 경우라는 것을 파악할 수 있다.

다시 1차원 배열로 돌아와서, 우리는 2차원 배열의 내용을 1차원 배열로 압축하여 표현하기 때문에 위 그림처럼 각각의 좌표로 접근할 수 없다. 그러나 1차원 배열의 인덱스는 열(Column)으로 사용하고 해당 인덱스의 원소값을 행(Row)값으로 사용하고 있기 때문에 Math.abs(i - row) === Math.abs(board[i] - board[row]) 가 참인 경우 대각선에 있다고 판단할 수 있을 것이다. 둘 사이의 간격을 구하는 것이기 때문에 절대값으로 구해주었다. 이를 바탕으로 isValid 함수를 다음과 같이 구현할 수 있다.

const isValid = (board, row) => {
  // 현재라인과 이전 라인을 검사하기 때문에
  // 1 - row 까지 반복하여 검사할 수 있다.
  for(let i = 1; i < row; i++) {
    // 같은 라인에 있는 경우 배치 불가
    if(board[i] === board[row]) return false;
    // 대각 라인에 있는 경우 배치 불가
    if(Math.abs(i-row) === Math.abs(board[i] - board[row])) return false;
  }
  // 위를 모두 통과하면 배치가 가능하다.
  return true;

N-Queen 문제는 이처럼 1차원 배열로 공간복잡도를 최적화 하는 방법 외에도 또 다른 최적화 방법이 많이 연구되었다. 만약 관심이 간다면 해당 방법을 찾아보는 것을 추천한다. 주석을 제외한 전체 코드는 다음과 같다.

function solution(n) {
  let answer = 0;
  
  const dfs = (board, row) => {
    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]) return false;
      if(Math.abs(board[i] - board[row]) === Math.abs(i - row)) return false;
    }
    return true;
  }
  
  for(let i = 1; i <= n; i++) {
    const board = new Array(n+1).fill(0);
    board[1] = i;
    dfs(board, 1);
  }
  
  return answer;
}
  

출처

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