[Leetcode] - 51

• brute-force를 할 때는 항상 중복되지 않게 해야함
  - 각 row 순서대로 어떤 col에 퀸 놓을지 결정

• backtracking
  1. col 을 바꿔가며 queen을 놓을 수 있는지 확인

  2. 놓을 수 있으면 퀸 이동 범위 마킹하고, 다음 row 탐색
  3. 탐색 종료되면 원래 상태로 돌려놓기

• diagonal (right upper, left upper) 의 row + col, row - col 은 같음

• queen 을 놓을 때

  • col 마킹
  • row+col 을 인덱스로 하는 부분 마킹
  • row-col 을 인덱스로 하는 부분 마킹

• 시간복잡도: O(N!)
  - row 의 퀸 위치를 결정할 때마다 다음 row에서 놓을 수 있는 개수가 2개씩 줄어든다
  (N(N-2)(N-4)...)

• 공간복잡도: O(N)
  - 퀸 개수

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        
        def could_place(row, col):
            if cols[col]:
                return False
            if hill_diagonals[row-col]:
                return False
            if dale_diagonals[row+col]:
                return False
            return True
        
        def place_queen(row, col):
            queens.add((row, col))
            cols[col] = True
            hill_diagonals[row-col] = True
            dale_diagonals[row+col] = True
        
        def remove_queen(row, col):
            queens.remove((row, col))
            cols[col] = False
            hill_diagonals[row-col] = False
            dale_diagonals[row+col] = False
        
        def add_solution():
            solution = []
            for _, col in sorted(queens):
                solution.append('.' * col + 'Q' + '.' * (n - col - 1))
            output.append(solution)
        
        def backtrack(row):
            for col in range(n):
                if could_place(row, col):
                    place_queen(row, col)
                    if row+1 == n:
                        add_solution()
                    else:
                        backtrack(row+1)
                    remove_queen(row, col)
        
        cols = [False for _ in range(n)]
        hill_diagonals = [False for _ in range(2*n-1)]
        dale_diagonals = [False for _ in range(2*n-1)]
        queens = set()
        output = []
        
        backtrack(row=0)
        
        return output