Backtracking: 51. N-Queens

51. N-Queens

 

https://youtu.be/Ph95IHmRp5M?si=nFzhZlWopNf9D4FI

 

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        """
        - negDiag:
            ↖ ↘ 대각선 방향을 추적 (row - col = 일정한 값)
        - posDiag:
            ↗ ↙ 대각선 방향을 추적 (row + col = 일정한 값)
        - col:
            퀸이 이미 배치된 열(column)을 추적
        - 매 줄마다 퀸 하나씩 배치 가능 (한 행에 하나의 퀸만 존재)
        """

        # 퀸이 배치된 열(column), 양수 대각선(posDiag), 음수 대각선(negDiag)을 추적하는 집합
        col = set()
        posDiag = set()  # r + c (양수 대각선 ↗ ↙)
        negDiag = set()  # r - c (음수 대각선 ↖ ↘)

        # 결과를 저장할 리스트
        res = []

        # 현재 체스판 상태를 나타내는 2D 리스트
        board = [["."] * n for i in range(n)]

        # 백트래킹 함수 정의
        def backtrack(r):  # 현재 처리 중인 행(row)
            # 기저 조건: n개의 퀸을 모두 배치한 경우
            if r >= n:
                # 현재 체스판 상태를 문자열 리스트로 변환하여 결과에 추가
                res.append(["".join(row) for row in board])
                return

            # 현재 행(r)에서 모든 열(c)을 순회하며 퀸 배치 시도
            for c in range(n):
                # 현재 열, 양수 대각선, 음수 대각선에 퀸이 이미 배치된 경우 건너뜀
                if c in col or (r + c) in posDiag or (r - c) in negDiag:
                    continue

                # 퀸을 현재 위치(r, c)에 배치
                col.add(c)  # 열 방문 처리
                posDiag.add(r + c)  # 양수 대각선 방문 처리
                negDiag.add(r - c)  # 음수 대각선 방문 처리
                board[r][c] = "Q"  # 체스판에 퀸 배치

                # 다음 행(r+1)으로 이동하여 퀸 배치 시도
                backtrack(r + 1)

                # 백트래킹: 현재 배치를 원래 상태로 되돌림
                board[r][c] = "."  # 퀸 제거
                col.remove(c)  # 열 방문 해제
                posDiag.remove(r + c)  # 양수 대각선 방문 해제
                negDiag.remove(r - c)  # 음수 대각선 방문 해제

        # 백트래킹 시작: 첫 번째 행부터 퀸 배치 시도
        backtrack(0)

        # 모든 가능한 퀸 배치 결과 반환
        return res

 

 

https://youtu.be/gcuZ_VGIcn4?si=a3HM3R6JjgZX9W9g