N-Queens

문제 파악

주어진 n x n 체스판 위에 n개의 퀸을 배치하는 문제(퀸은 같 행, 열, 대각선 공격 가능) N-Queens - LeetCode

접근 방법

백트래킹을 사용하여 가능한 모든 퀸의 배치를 탐색한다.

1. 순회를 돌면서 각 위치에 퀸을 놓을때, 해당 위치가 다른 퀸과 충돌하지 않는지 확인
2. 가능한 경우 해당위치에 퀸을 놓고 다음 행으로 이동
3. 모든 행에 퀸을 놓은 경우 해당 배치 결과를 리스트에 추가

코드 구현

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def is_valid(x, y):
            # 가로세로
            for i in range(n):
                if board[x][i] == 'Q' or board[i][y] == 'Q':
                    return False
                
            # 대각선 체크 
            for i in range(n):
                for j in range(n):
                    if (i + j == x + y or i - j == x - y) and board[i][j] == 'Q':
                        return False
                    
            return True
                    
        def backtrack(row):
            # base case
            if row == n:
                ans.append([''.join(row) for row in board])
                return
            
            for col in range(n):
                if is_valid(row, col):
                    board[row][col] = 'Q'
                    backtrack(row + 1)
                    board[row][col] = '.'
            
        
        board = [['.']*n for _ in range(n)]
        ans = []
        backtrack(0)
        return ans

배우게 된 점