51. N-Queens

N-Queens - LeetCode

 

설명할 필요 없는 N-Queens 문제를 구현해보자.

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

 

1. DFS, 백트래킹

from typing import *


class Solution:

    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        board, cols = [0] * n, [0] * n
        left_div, right_div = [0] * (2 * n), [0] * (2 * n)

        def record(board):
            answer = []
            default = ["."] * n
            for i in range(n):
                default[board[i]] = "Q"
                answer.append("".join(default))
                default[board[i]] = "."
            return answer

        def is_possible(row, col):
            if cols[col]:
                return False
            if left_div[n - (col - row)]:
                return False
            if right_div[row + col]:
                return False
            return True

        def dfs(row):
            if row == n:
                res.append(record(board))
                return
            for col in range(n):
                if is_possible(row, col):
                    board[row] = col
                    cols[col] = 1
                    left_div[n - (col - row)] = 1
                    right_div[row + col] = 1
                    dfs(row + 1)
                    cols[col] = 0
                    left_div[n - (col - row)] = 0
                    right_div[row + col] = 0

        dfs(0)
        return res

 

N-Queens 문제는 굉장히 최적화를 할 수 있는 부분이 많다.

 

1. (당연하지만) 백트래킹을 사용하면 더 빠르게 결과를 얻을 수 있다.
2. 체스판을 추상화하는 2차원 배열 대신 1차원 배열로 해결할 수 있다.
3. while문으로 반복해 현재 경로에 Queen이 있는지 체크하는 것 대신 미리 방문 배열을 만들어서 (row, col)에 놓을 수 있는지 바로 확인할 수 있다.
4. (이해하기 어려운 부분) 만일 구하는 게 가짓수라면 대칭이 되는 경우는 굳이 탐색하지 않아도 구할 수 있다.

이 문제는 조건을 만족하는 패턴을 구해야 하기 때문에 3번까지는 최적화를 할 수 있다. 만일 가짓수를 구하는 문제였다면 4번까지 적용해 더 적은 탐색으로 결과를 구할 수 있다. 자세하게 알고 싶다면 N-Queens 최적화로 검색하면 잘 정리된 포스트들이 나온다.

 

알고리즘 공부를 해야겠다고 맘먹게 해 준 문제라 나에겐 굉장히 뜻깊은 문제.