52. N-Queens II

52. N-Queens II

 

문제 설명: N-Queens II

N-Queens 문제는 n×n 체스판에서 n개의 퀸을 서로 공격하지 않도록 배치하는 문제입니다.

이 문제의 목표는 모든 가능한 배치 방법의 개수를 찾는 것입니다.

---

퀸(Queen)의 공격 조건

퀸은 다음의 위치에 있는 다른 퀸을 공격할 수 있습니다:

1. 같은 행에 있는 퀸
2. 같은 열에 있는 퀸
3. 대각선에 있는 퀸 (왼쪽 위 ↖, 오른쪽 위 ↗, 왼쪽 아래 ↙, 오른쪽 아래 ↘)

즉, 어떤 퀸도 서로 같은 행, 같은 열, 또는 대각선에 위치할 수 없습니다.

---

문제 예제

예제 1: n=4

출력: 2

설명:

• 4×4 체스판에 퀸을 배치할 수 있는 경우의 수는 2개입니다.

예제 2: n=1

출력: 1

설명:

• 1×1 체스판에서는 퀸을 1개만 배치할 수 있으므로, 가능한 배치 방법은 1개입니다.

---

풀이 방법: 백트래킹 (Backtracking)

백트래킹은 가능한 모든 경우를 시도하면서, 조건에 맞지 않는 경우를 빠르게 배제하는 방식입니다.

풀이의 주요 단계

1. 각 행(row)에 퀸을 하나씩 배치:
   • 첫 번째 행부터 마지막 행까지 퀸을 배치합니다.
   • 한 행에 퀸을 배치하면, 다음 행으로 이동합니다.
2. 배치 조건 확인:
   • 퀸이 서로 같은 열에 있는지 확인.
   • 퀸이 대각선에서 서로 공격할 수 있는지 확인.
3. 모든 행에 퀸을 배치하면 경우의 수를 증가:
   • 유효한 배치를 찾으면 배치 수를 증가시키고, 탐색을 종료합니다.
4. 백트래킹:
   • 현재 행에서 가능한 모든 배치를 시도한 후, 퀸을 제거하고 이전 단계로 돌아갑니다.

코드 동작 과정

입력 예제: n=4

1. 첫 번째 행(row=0):
   • 첫 번째 열(col=0)에 퀸을 배치.
   • 이후 백트래킹으로 다음 행(row=1)으로 이동.
2. 두 번째 행(row=1):
   • 공격하지 않는 열(col=2)에 퀸 배치.
   • 다음 행(row=2)로 이동.
3. 세 번째 행(row=2):
   • 유효한 열(col=1)을 찾고 퀸 배치.
   • 다음 행(row=3)로 이동.
4. 네 번째 행(row=3):
   • 유효한 열(col=3)을 찾고 퀸 배치.
   • n개의 퀸 배치 완료 → 카운트 증가.
5. 백트래킹:
   • 마지막 행(row=3)에서 다른 가능한 배치 확인.
   • 조건에 맞지 않는 경우를 제거하며 다른 경우 탐색.

---

시간 복잡도

• 백트래킹은 모든 가능한 배치를 시도하므로, 최악의 경우 **O(n!)**의 시간 복잡도를 가집니다.
• 하지만 가지치기(Pruning)로 불필요한 탐색을 줄여 효율성을 높입니다.

---

결과

• n=4: 2
• n=1: 1
• 최대 n=9까지 효율적으로 해결 가능합니다.

 

https://youtu.be/nalYyLZgvCY?si=5i6NCC6phHeTNWlR

 

 

class Solution:
    def totalNQueens(self, n: int) -> int:
        # 열을 추적하기 위한 집합 (어떤 열에 퀸이 배치되었는지 기록)
        col = set()
        
        # 양의 대각선을 추적하기 위한 집합 (행 + 열로 계산되는 대각선 구분)
        posDiag = set() # (r + c)
        
        # 음의 대각선을 추적하기 위한 집합 (행 - 열로 계산되는 대각선 구분)
        negDiag = set() # (r - c)
        
        # 결과값을 저장하는 변수 (가능한 퀸 배치의 총 개수)
        res = 0

        # 백트래킹 함수 정의 (현재 행 r에서 퀸을 배치하기 위한 탐색)
        def backtrack(r):
            # 베이스 케이스: 모든 행에 퀸을 배치한 경우
            if r == n: # 마지막 행까지 퀸 배치를 완료했다면
                nonlocal res  # 외부 변수 res를 수정하기 위해 선언
                res += 1  # 가능한 배치 방법 추가
                return

            # 현재 행 r에서 모든 열 c를 순회하며 퀸 배치 시도
            for c in range(n):
                # 열, 양의 대각선, 음의 대각선에 이미 퀸이 배치된 경우 건너뛴다
                if (c in col or 
                    (r + c) in posDiag or
                    (r - c) in negDiag):
                    continue  # 해당 열/대각선은 사용할 수 없으므로 스킵
                
                # 현재 열과 대각선을 사용 중으로 표시
                col.add(c)  # 열 c에 퀸 배치
                posDiag.add(r + c)  # 양의 대각선 (r + c)에 퀸 배치
                negDiag.add(r - c)  # 음의 대각선 (r - c)에 퀸 배치

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

                # 백트래킹: 퀸을 제거하고 현재 상태를 초기화
                col.remove(c)  # 열 c에서 퀸 제거
                posDiag.remove(r + c)  # 양의 대각선에서 퀸 제거
                negDiag.remove(r - c)  # 음의 대각선에서 퀸 제거
        
        # 탐색 시작: 첫 번째 행부터 퀸 배치 시도
        backtrack(0)
        
        # 가능한 모든 배치 방법의 개수를 반환
        return res