Leetcode Java N-Queens

문제

Link

코드

class Solution {

  public List<List<String>> solveNQueens(int n) {
    char[][] board = new char[n][n];
    for (char[] row : board) {
      Arrays.fill(row, '.');
    }
    List<List<String>> result = new ArrayList<>();
    this.dfs(n, board, result, 0, new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1]);
    return result;
  }

  private void dfs(int n, char[][] board, List<List<String>> result, int i, boolean[] cols, boolean[] diagonals1, boolean[] diagonals2) {
    if (i == n) {
      List<String> list = new ArrayList<>();
      for (char[] row : board) {
        list.add(new String(row));
      }
      result.add(list);
    } else {
      for (int j = 0; j < cols.length; j++) {
        if (!cols[j] && !diagonals1[i + j] && !diagonals2[j - i + n - 1]) {
          board[i][j] = 'Q';
          cols[j] = diagonals1[i + j] = diagonals2[j - i + n - 1] = true;
          this.dfs(n, board, result, i + 1, cols, diagonals1, diagonals2);
          cols[j] = diagonals1[i + j] = diagonals2[j - i + n - 1] = false;
          board[i][j] = '.';
        }
      }
    }
  }

}

결과

Link

설명

1. $n \times n$ 크기의 체스판 내 n개의 퀸을 배치하였을 때, 서로 공격할 수 없는 위치의 배치들을 반환하는 문제이다.
   • 문자 ‘Q’는 퀸을, 문자 ‘.’은 빈 공간을 의미한다.
2. 문제 풀이에 필요한 변수를 정의한다.
   • board는 체스판을 구성할 변수로, $n \times n$ 크기의 문자 배열로 초기화 후 모든 위치에 ‘.’ 문자를 넣어준다.
   • result는 결과를 저장할 변수로, ArrayList로 초기화한다.
3. DFS 방식으로 퀸이 서로 공격하지 못하는 체스판을 구성할 dfs(int n, char[][] board, List<List> result, int i, boolean[] cols, boolean[] diagonals1, boolean[] diagonals2) 메서드를 정의한다.
   • i가 n인 마지막 위치인 경우, board의 각 행을 문자열로 변환하여 넣은 ArrayList를 모두 넣어준다.
   • i가 n인 마지막 위치가 아닌 경우, 0부터 cols의 길이 미만까지 j를 증가시키며 아래를 반복한다.
     • cols[j], diagonals1[$i + j$], diagonals2[$j - i + n - 1$] 값이 모두 true이면 다음 반복을 수행한다.
     • board[i][j]의 위치에 ‘Q’를 넣어 퀸을 위치시킨다.
     • cols[j], diagonals1[$i + j$], diagonals2[$j - i + n - 1$] 값에 모두 true를 넣어, 공격 가능한 위치를 체크해준다.
     • i 위치에 $i + 1$을 넣어 재귀 호출을 수행해준다.
     • cols[j], diagonals1[$i + j$], diagonals2[$j - i + n - 1$] 값에 모두 false를 넣어, 해당 위치를 초기화시켜준다.
     • board[i][j]의 위치에 ‘.’를 넣어 퀸도 제거해준다.

4. 3번의 dfs(int n, char[][] board, List<List> result, int i, boolean[] cols, boolean[] diagonals1, boolean[] diagonals2) 메서드를 i에 0, cols는 n 크기의 부울 배열, diagonals1과 diagonals2는 $2 * n - 1$ 크기의 부울 배열을 넣어 수행해준다.

5. 반복이 완료되면 각 위치가 저장된 result를 주어진 문제의 결과로 반환한다.

소스

Sample Code는 여기에서 확인 가능합니다.