LeetCode 51번 N-Queens

https://leetcode.com/problems/n-queens/

---

문제 파악

N-Queens 문제는 n x n 체스판에 n개의 퀸을 서로 공격하지 않게 배치하는 문제이다. 퀸은 같은 행, 열, 대각선에 있는 다른 퀸을 공격할 수 있다.

접근 방법

백트래킹은 문제를 해결할 수 있는 모든 가능한 조합을 탐색하는 방식이다. 이 문제에서는 각 퀸이 서로 공격할 수 없도록 배치하는 모든 가능한 조합을 찾는다. 퀸을 체스판에 배치할 때, 다음과 같은 제약 조건이 있다.

1. 같은 행에 두 퀸이 있을 수 없습니다.
2. 같은 열에 두 퀸이 있을 수 없습니다.
3. 같은 대각선에 두 퀸이 있을 수 없습니다.

그렇기 때문에 다음과 같은 순서로 백트래킹을 진행한다.

1. 한 줄씩 보드에 퀸을 배치한다.
2. 현재 줄에 퀸을 놓을 수 있는 위치를 찾아, 유효한 경우에만 다음 줄로 이동한다.
3. 모든 퀸이 배치되면, 보드를 결과 리스트에 추가한다.
4. 그렇지 않으면, 다른 가능한 위치로 퀸을 옮겨서 다시 시도한다.

코드 구현

from typing import List

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        # 보드 생성
        def create_board(state: List[int]) -> List[str]:
            # 보드 초기화
            board = []
            for i in range(n):
                row = ['.'] * n
                # state 리스트 값에 따라 현재 행의 특정 위치에 퀸 배치
                row[state[i]] = 'Q'
                # 문자열로 변환
                board.append(''.join(row))
            return board

        def backtrack(row: int):
            # Base Case : row가 n에 도달할 때
            if row == n:
                solutions.append(create_board(state))
                return

            # 열과 대각선의 유효성 검사
            for col in range(n):
                if col in columns or (row - col) in diag1 or (row + col) in diag2:
                    continue

                # 퀸 배치
                state[row] = col
                columns.add(col)
                
                # 퀸의 현재 위치를 대각선 집합에 추가하여 추적
                diag1.add(row - col)
                diag2.add(row + col)

                # 다음 행 탐색
                backtrack(row + 1)

                # 퀸 제거
                columns.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)

        # 보드 상태 추적
        solutions = []
        state = [-1] * n  
        columns = set()  
        diag1 = set()  
        diag2 = set()  

        backtrack(0)
        return solutions

배우게 된 점

유효성 검사와 재귀적 탐색을 통해 문제를 효율적으로 푸는 법에 대해 생각해보게 되었다.