[ LeetCode - 52 ] N-Queens II

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

N-Queens II - LeetCode

유명한 N-Queen 문제, 딱 한번 고생해서 했더니 그 다음부터는 다시 풀어도 수월하게 풀리는거 같다.

---

[ 📌 풀이 ]

중요한건 퀸을 어느 발판이 나뒀는지인데 신경써야할점은 총 3가지다.

 

• row) 어느 줄에 퀸을 두었는가?

[ row ]

퀸이 같은 row(줄)에 존재하면 조건이 성립될 수 없기 때문에 이를 판단해 줘야한다.

visited 배열을 두어서 해당 퀸을 둘 때마다 해당 row에 True 처리를 해준다.

 

• 대각선1)

[ 대각선 1]

대각선에 대해서도 처리를 해줘야 하는데 대각선은 그림에서 보면 8 *8 사이즈에 체스판에서 총 15개의 선이 나오는데 이는 n이 주어졌을 때 n * 2 -1 만큼의 수다.

 

각 대각선에 대해서 관리를 하기 위해서는 인덱스가 필요한데 각 대각선의 숫자는 좌표 x + y에 해당하는 값이다.

 

• 대각선2)

[ 대각선2 ]

이전 대각선1과 설명은 같지만 인덱스 채번이 다르게 되어있는데, x + y를 하면 좌우 대칭되는 인덱스가 나오게 된다.

그래서 x - y를 하게 되었는데, 이렇게 되면 음수가 나오고 음수는 배열의 인덱스로 사용이 불가능하다. (파이썬은 가능하지만 제어가 쉽지 않을듯) 그래서 각 인덱스에 +7 (주어진 n에 -1을 한 값)을 하게 되면 반대 대각선과 같은 인덱싱이 가능하다.

 

⚙︎ column에 대해서는 따로 T/F 체크를 하지 않는데 backtracking 로직을 보면 for문에서 보이는 idx가 column에 해당한다.

for문에 의해서 제어되어 column에 대해서는 중복될 수 없기 때문에 따로 관리하지 않는다.

---

[ 📌 코드 - Python ]

"""
# Author    : Lee In Bok 
# Date      : 2023.10.29(Sun)
# Spend Time: 미측정 (X)
# Runtime   : 58 ms (Beats 44.52%)
# Memory    : 16.1 MB (Beats 85.44%)
# Algoritm  : Backtracking
"""

class Solution:
    def totalNQueens(self, n: int) -> int:
        self.ans, self.n = 0, n
        self.vis1 = [0 for _ in range(n)]
        self.vis2 = [0 for _ in range(n * 2 -1)]
        self.vis3 = [0 for _ in range(n * 2 -1)]

        self.backtracking(0)    # 0번 row부터 시작
            
        return self.ans
    
    def backtracking(self, row: int):
        if row == self.n:
            self.ans += 1
            return

        for idx in range(self.n):
            if not self.vis1[idx] and not self.vis2[idx + row] and not self.vis3[row - idx + (self.n - 1)]:
                self.vis1[idx] = self.vis2[idx + row] = self.vis3[row - idx + (self.n - 1)] = True
                self.backtracking(row + 1)
                self.vis1[idx] = self.vis2[idx + row] = self.vis3[row - idx + (self.n - 1)] = False

s = Solution()
result = s.totalNQueens(8)

print(result)

---

[ 📌 결과 ]

[ Result ]

---

[ 📌 N-Queen 맨 처음 접했을 때 규칙을 찾기위한 노력 ]

[ 나의 노력 ]