51. N-Queens

문제링크: https://leetcode.com/problems/n-queens/

n*n 체스판에서 n개의 퀸을 놓을 수 있는 모든 경우의 수를 찾는다.

Solution

1. Backtracking in matrix

일반적인 매트릭스에서의 완전탐색을 통해 접근해 보기로 했다. Q를 놓게 되면 가로, 세로, 대각선에 더 이상 놓지 못하도록 'X'마킹을 하고 해당 깊이에서 표시한 곳들을 stack에 저장한다. 이후 깊이 탐색을 끝낸 후 다시 돌아오면 stack에 저장되있는 마킹부분을 pop해 마킹한 부분을 다시 원상복구 시킨다. JS 문자열에서 하나를 수정하려면 새 문자열을 만들어서 넣어야하기 때문에 chess를 이중배열로 만들고 결과에만 문자열로 변환했다.

Algorithm

• chess배열을 만들어 0으로 채운다. (0은 '.'과 같다)
• dfs(0, 0, 0) 부터 완전탐색을 시작한다.
• count 여태 놓은 말의 개수가 목표치와 같으면 chess의 결과를 알맞은 포맷으로 바꿔 결과에 넣는다.
• 아닌 경우 r, c의 좌표부터 말을 놓을 수 있는지(chess[i][j] === 0) 확인한다.
• 말을 놓을 수 있는 경우 mark함수를 통해 현재 놓는 말 위치와 영향을 주는 타일(가로,세로,대각)을 마킹하고 마킹한 지역을 myMark에 숫자로 인코딩해 저장한다.
• 말을 놓았으면 현재 좌표 이후로 dfs(새좌표, count+1)로 깊이 우선탐색을 한다.
• 탐색이 끝난 후 myMark의 값을 이용해 erase로 마킹했던 지역을 다시 초기화하고 다음 타일을 탐색한다.

var solveNQueens = function(n) {
  // n개의 퀸을 n*n 체스에 넣는 방법
  // 1. 백트래킹: 매트릭스 백트래킹은 표시를 잘 해야 한다.
  // 놓은 곳을 2, 못놓는 곳을1로 표시하고 최근에 표시한 부분은 스택에 저장 (마킹을 되돌릴 때 사용)
  const result = [];
  
  const chess = new Array(n);
  for (let i = 0; i < n; i++) {
    chess[i] = new Array(n).fill(0);
  }  
  
  const mark = (r, c) => {
    const markedArr = [];
    // 자기자리
    chess[r][c] = 2;
    markedArr.push(r * 10 + c);
    
    // 세로
    for (let i = 0; i < n; i++) {
      if (i !== r && chess[i][c] === 0) {
        chess[i][c] = 1;
        markedArr.push(i*10 + c);
      } 
    }
    // 가로
    for (let j = 0; j < n; j++) {
      if (j !== c && chess[r][j] === 0) {
        chess[r][j] = 1;
        markedArr.push(r*10 + j);
      }
    }
    // 왼대각
    for (let i = 1; i + r < n && i + c < n; i++) {
      if (chess[r + i][c + i] === 0) {
        chess[r + i][c + i] = 1;
        markedArr.push((r+i)*10 + c+i);
      }
    }
    for (let i = -1; i + r >= 0 && i + c >= 0; i--) {
      if (chess[r + i][c + i] === 0) {
        chess[r + i][c + i] = 1;
        markedArr.push((r+i)*10 + c+i);
      }
    }
    // 오른대각
    for (let i = 1; r - i >= 0 && c + i < n; i++) {
      if (chess[r - i][c + i] === 0) {
        chess[r - i][c + i] = 1;
        markedArr.push((r-i)*10 + c+i);
      }
    }
    for (let i = 1; r + i < n && c - i >= 0; i++) {
      if (chess[r + i][c - i] === 0) {
        chess[r + i][c - i] = 1;
        markedArr.push((r+i)*10 + c-i);
      }
    }
    return markedArr;
  }
  const erase = (markedArr) => {
    for (let num of markedArr) {
      const r = parseInt(num / 10);
      const c = num % 10;
      chess[r][c] = 0;
    }
  }
  
  const dfs = (r, c, count) => {
    if (count === n) {
      const res = [];
      chess.forEach((arr) => {
        res.push(arr.join("").replaceAll(/0|1/g,'.').replace('2','Q'));
      });
      result.push(res);
      return;
    }
    let i = r, j = c;
    while (i < n) {
      if (chess[i][j] === 0) {
        const myMark = mark(i, j);
        j + 1 === n ? dfs(i + 1, 0, count + 1) : dfs(i, j + 1, count + 1);
        erase(myMark);
      }
      
      // 내려가기
      if (++j === n) {
        j = 0;
        i++;
      }
    }
  }
  
  dfs(0, 0, 0);
  return result;
};

못 놓는 곳을 직접 마킹하기 때문에 마킹과 마킹지우기에 필요한 추가적인 시간들이 n에 비례하게 된다.

2. Backtracking row by row

퀸은 같은 row에 하나씩만 넣을 수 있고 꼭 들어가야 한다. 따라서 이를 row의 관점에서 보면 어느 row에 넣을지를 선택해 탐색하는 것으로 생각할 수 있다. row 해당 row에서 모든 col Index에 대해 가능한지는 현재 존재하는 chess.length에 비례한다.(확인해야하는 칸은 대각,세로 3가지 경우의 수씩만 존재) 이를 통해 row별로 퀸을 생성 가능한 곳에 생성하고 dfs 백트래킹을 진행해 보았다.

Algorithm

• dfsRow 재귀 함수를 통해 가능한 경우의 수를 찾는다.
• chess가 모두 완성된 경우 결과를 복사해 result에 넣는다.
• 새 row를 만들기 위해서 row중 어느 col index에 퀸을 넣어도 되는지 탐색한다.
• 탐색하는 방법은 기존에 존재하는 row의 세로, 대각 위치에 다른 퀸이 존재하는지 확인한다.
• 다른 퀸이 존재하지 않는 경우 해당 위치에 퀸이 존재하는 배열을 push하고 깊이 탐색을 한다.
• 탐색이 끝난 후 pop을 통해 사용했던 퀸row를 제거한다.

var solveNQueens = function(n) {
  // n개의 퀸을 n*n 체스에 넣는 방법
  // 백트래킹 row by row : 퀸은 row 당 하나만 넣을 수 있음을 통해 row에 하나씩 넣고 탐색하는 방법
  const result = [];
  const chess = [];
  const dfsRow = () => {
    if (chess.length === n) result.push(chess.slice(0));
    const nextQueenRow = chess.length;
    for (let i = 0; i < n; i++) {
      // 다음 row에 퀸을 넣을 좌표 i선택
      // 퀸을 이자리에 넣어도 되는지 이미 체스에 존재하는 퀸들과 비교해 확인
      let canPutQueen = true;
      for (let j = 0; j < nextQueenRow; j++) {
        // 다른 말이 수직, 대각선에 존재할 경우 넘어감
        if ( (chess[j][i] === 'Q') || (chess[j][i - nextQueenRow + j] === 'Q') || (chess[j][i + nextQueenRow - j] === 'Q') ) {
          canPutQueen = false;
          break;
        }
      }
      // chess.push 퀸을 넣고 dfs
      if (canPutQueen) {
        chess.push(".".repeat(i) + 'Q' + '.'.repeat(n - i - 1));
        dfsRow();
        // dfs끝나면 chess.pop()
        chess.pop();
      }

    }
  }
  dfsRow();
  return result;
};

1번의 방법과 크게 다른 부분은 하향식으로 탐색하기 때문에 탐색시 상단의row 부분만 고려한다는점, 백트래킹을 위해 chess에 데이터를 넣고 탐색후 다시 제거하는 과정에서 repeat부분을 제외하면 거의O(1)의 시간복잡도로 백트래킹 재귀를 할 수 있다는 점이다. 불필요한 인코딩 디코딩, 결과를 도출하기 위한 타입변환 제거 등 문제 결과 도출에도 적합한 방법으로 개선할 수 있었다.