프로그래머스: N-Queen

Posted Jul 12, 2024

By Jeongeun Lee

13 min read

프로그래머스: N-Queen

N-Queen

한 변의 길이가 n인 정사각형 체스판 위에 n개의 퀸을 서로 한 번에 공격할 수 없도록 배치하는 경우의 수 구하기
제한 조건
1 ≤ N ≤ $12$ 인 자연수
문제 풀이 조건
퀸은 가로, 세로, 대각선 방향으로 이동할 수 있음.

알고리즘 구상하기

서로 공격할 수 없는 조건 정리하기

문제를 해결하는데 가장 어려웠던 점은 대각선 방향을 고려하는 것이었다. 가로, 세로 방향은 동일한 row, column에 퀸을 배치하지 않으면 해결되었으나, 대각선 방향에 대해서는 어떻게 조건화해야 할지 고민했다.
이에 따라, 우선 대각선 방향으로 배치되는 퀸들은 어떤 규칙을 가질지 파악하고자 했다.

먼저 퀸을 임의의 체스판 위치 (a, b)에 배치했다고 가정했다. 여기서 체스판은 이중배열 board로 표현하며, a는 row, b는 column을 의미한다. 이를 코드로 표현하면 board[a][b]이다.
문제의 조건에서 n은 자연수이고 체스판의 단위길이는 1이기 때문에, 좌표가 변화하는 단위도 1로 하였다. 그리고 이 위치를 기준으로 대각선 방향에 둔 체스의 좌표 변화를 분석하였다.

그 결과, (a, b)를 기준으로 대각선 방향에 체스를 둘 때마다 좌표가 (±1, ±1)씩 변화한다는 사실을 알 수 있었다.
가령, board[a][b]에서 왼쪽 아래 방향으로 대각선을 그리며 이동하면, 위치는 board[a+1][b-1], board[a+2][b-2], board[a+3][b-3]…이 된다. 즉, row가 1씩 변화하면 column도 1씩 변화하는 것이다. 이는 대각선을 그리면 방향과 상관없이 동일하게 적용되는 규칙이다.

이에 따라, 퀸의 배치 조건을 다음과 같이 정리했다.

모든 퀸은 서로 다른 column값을 가진다.
모든 퀸은 서로 다른 row값을 가진다.
각 퀸들의 row값의 차이는 column값의 차이와 다르다.

ex ) 퀸A와 퀸B의 row값의 차이가 3이라면, column값의 차이는 3이 되어서는 안된다.

적절한 알고리즘: DFS

1차 시도: 재귀 함수를 이용해 row, column이 다른 경우를 모두 구하기

서로 공격할 수 없는 조건을 토대로, 우선 row, column이 서로 다른 경우를 모두 구하였다. 그리고 이들 중 서로의 row값 차이가 column값 차이와 다른 경우들만 추가로 선별하는 방식으로 코드를 구현했다.

row와 column이 서로 다른 경우를 구하는건 간단했다. 우선 체스판을 뜻하는 배열 board를 만들고, 각 배열의 index를 row의 index로 간주했다. 배열의 요소는 각 row에 놓인 퀸의 column index로 설정했다.
즉, 배열 요소의 index는 체스판 row의 index이며, 배열 요소는 column의 index인 것이다.

그리고 반복문을 이용해 배열 board를 row 0번부터 채워나갔다. 이때, 이 알고리즘을 재귀함수 setQueen() 내부에 구현하여 서로 다른 column index로 배열이 채워지도록 했다.

위와 같은 과정을 거쳐 1차 board 후보들이 완성되면, 대각선으로 공격하지 못하는 조건을 체크했다.
우선 반복문을 이용해 board의 row를 순회했다. 이때, 현재 타겟이 되는 row 이전의 row 값을 이중 반복문으로 체크하여 이전 row와 현재 row의 index의 차이가 각 column index의 차이와 동일한지 확인하고, 하나라도 동일하면 유효하지 않는 board로 분리했다.

구현한 코드는 다음과 같다.

  
function solution(n) {
  const boards = [];
  const setQueen = (board, visited) => {
    if (board.length === n) {
      boards.push(board);
      return;
    }

    for (let i = 0; i < n; i += 1) {
      const newBoard = [...board];
      const newVisited = new Set(visited);
      if (!visited.has(i)) {
        newBoard.push(i);
        newVisited.add(i);
        setQueen(newBoard, newVisited);
      }
    }
  };

  setQueen([], new Set());

  const answer = [];
  boards.forEach((board) => {
    let isAnswer = true;
    for (let currentRow = 0; currentRow < n; currentRow += 1) {
      for (let prevRow = 0; prevRow < currentRow; prevRow += 1) {
        const current = board[currentRow];
        const prev = board[prevRow];
        if (Math.abs(current - prev) === Math.abs(currentRow - prevRow)) {
          isAnswer = false;
          break;
        }
      }
    }

    if (isAnswer) answer.push(board);
  });

  return answer.length;
}

그러나 위 코드는 시간 효율적인 면에서 채점 기준을 통과하지 못하여, 오답처리되었다. 이에 따라, 시간복잡도를 줄이는데 집중하여 한 번 더 코드를 리팩토링했다.

2차 시도: 반복문을 이용한 DFS

우선, 재귀함수로 구현된 코드를 반복문으로 수정했다.

코드 길이나 가독성면에서는 개인적으로 재귀함수가 깔끔하게 느껴졌지만 스택 오버플로우와 같은 메모리 문제를 고려하여 반복문으로 변경했다.
그리고 퀸의 가로, 세로 공격 조건과 대각선 공격 조건을 한 번의 반복에서 처리하도록 수정했다.

이전 코드는 가로, 세로 공격 조건 충족하지 않도록 row, column을 배치하여 1차로 board 목록을 만들었다. 그리고 이 board 목록을 이중 반복문으로 한 번 더 순회하여 대각선 공격 조건을 충족하지 않는지 판별했다. 즉, 같은 board을 여러번 순회하였고, 이러한 불필요한 반복이 시간 효율성을 떨어뜨렸다.

이에 따라, 가로, 세로 공격 조건을 판별하는 로직에 대각선 공격 조건을 추가했다.

세부 로직 구상하기

이전 풀이에서는 완성된 board를 순회하며 row의 차와 column의 차를 비교했었다. 그러나 이번에는 미완성된 board를 문제의 조건에 맞게 배치하는 과정에 대각선 판별 조건이 추가가 되어야 했다. 이에 따라 이전 row에 배치한 퀸들의 column을 확인하여 현재 row에서 배치할 수 없는 column 목록을 만들기로 했다.

board 배열의 요소, 즉, column index를 reduce로 순회하며 여기에 현재 row index와 타겟 row index의 차 만큼 더하거나 뺐다. 계산된 값들은 현재 row에서 퀸을 배치할 수 없는 column들이다.
이들을 Set에 추가하여 금지목록 targetBan을 만들었다.

마지막으로 targetBan과 이전 row들에 배치된 퀸의 column index 목록, 즉, visited에 타겟 column이 존재하는지 확인하고 없으면 board의 새로운 요소로 추가하도록 로직을 완성했다.

그 결과, 다음과 같은 코드가 완성되었다.

[JavaScript]

  
function solution(n) {
  const boards = [];
  const queue = [{ board: [], visited: new Set() }];
  while (queue.length > 0) {
    const { board, visited, banned } = queue.pop();
    if (board.length === n) {
      boards.push(board);
      continue;
    }

    for (let i = 0; i < n; i += 1) {
      const currentIndex = board.length;
      const newBoard = [...board];
      const newVisited = new Set(visited);
      const targetBan = board.reduce((acc, cur, index) => {
        const diff = currentIndex - index;
        acc.add(cur + diff);
        acc.add(cur - diff);

        return acc;
      }, new Set());

      if (!visited.has(i) && !targetBan.has(i)) {
        newBoard.push(i);
        newVisited.add(i);
        queue.push({ board: newBoard, visited: newVisited });
      }
    }
  }

  return boards.length;
}

3차 시도: 금지목록 로직을 반복문에서 분리하기

그러나 2번째로 시도한 코드도 시간복잡도 문제를 피할 수 없었다. 이에 따라, 시간복잡도를 더 줄일 수 있을지 고민했다.

코드를 찬찬히 살펴본 결과, 문제점 하나를 발견할 수 있었다. 바로 targetBan 데이터를 생성하는 로직의 위치였다.
이 데이터는 이전 row의 값들을 이용하여 생성된 후 다음 row로 넘어가기 전까지 바뀌지 않는다.
즉, 가로, 세로, 대각선 조건을 체크하고 board를 생성하는 로직 내부에 위치할 필요가 없이, 한 번만 실행되어도 되는 로직이었던 것이다.

이에 따라, 불필요하게 반복되었던 targetBan 생성 로직을 반복문 외부로 빼내어 아래와 같은 코드를 완성했다. 다행히 이 코드는 무사히 통과하여 최종 로직이 되었다.

[JavaScript]

  
function solution(n) {
  const boards = [];
  const queue = [{ board: [], visited: new Set() }];
  while (queue.length > 0) {
    const { board, visited } = queue.pop();
    if (board.length === n) {
      boards.push(board);
      continue;
    }

    const targetBan = board.reduce((acc, cur, index) => {
      const diff = board.length - index;
      acc.add(cur + diff);
      acc.add(cur - diff);
      return acc;
    }, new Set());

    for (let i = 0; i < n; i += 1) {
      const newBoard = [...board];
      const newVisited = new Set(visited);

      if (!visited.has(i) && !targetBan.has(i)) {
        newBoard.push(i);
        newVisited.add(i);
        queue.push({ board: newBoard, visited: newVisited });
      }
    }
  }

  return boards.length;
}

What I Learn, Algorithm

This post is licensed under CC BY 4.0 by the author.