[DSA][Backtracking] 10. N-Queens

LeetCode 51

 

10. N-Queens

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

 

[질문하기]

- 항상 유효한 해가 존재하나요? 해가 없는 경우에는 빈 리스트를 반환하면 되나요? YES

 

[아이디어]

- 퀸의 충돌 여부를 판단한 후 backtracking으로 기물을 배치한다.

 

[풀이 1] Backtracking

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res, tmp = [], []
        
        def coordToStr(res):
            strRes = []
            for coord in res:
                tmpRes = []
                for i, j in coord:
                    tmpRes.append("." * j + "Q" + "." * (n - j - 1))
                strRes.append(tmpRes)
            return strRes

        def noAttack(x, y):
            for i, j in tmp:
                if i == x or j == y:
                    return False
                
                if abs((i - x) / (j - y)) == 1:
                    return False
            return True

        def dfs(cnt,i):
            if cnt == n:
                res.append(tmp.copy())
                return
            
            for j in range(n):
                if noAttack(i, j):
                    tmp.append((i, j))
                    dfs(cnt + 1, i + 1)
                    tmp.pop()
            return
        
        for j in range(n):
            tmp.append((0, j))
            dfs(1, 1)
            tmp.pop()
        
        return coordToStr(res)

이 풀이는 별도의 최적화 없이, 문제의 조건을 그대로 구현한 백트래킹 풀이이다.

N-Queens 문제에서는 한 행(row)에 퀸을 두 개 이상 놓을 수 없으므로, 각 행마다 하나의 퀸을 배치하는 방식으로 탐색을 진행한다. 현재 행에서 열(col)을 0부터 n−1까지 순회하며, 해당 위치에 퀸을 놓을 수 있는지 검사한 뒤 가능한 경우에만 다음 행으로 DFS를 수행한다.

DFS 과정에서는 새로 배치하려는 퀸이, 지금까지 배치된 퀸들과 서로 공격하지 않는지를 판단한다. 이를 위해 기존에 놓인 모든 퀸의 좌표를 순회하며 다음 세 가지 조건을 검사한다.

• 같은 행(row)에 위치하는지
• 같은 열(col)에 위치하는지
• 두 좌표의 행 차이와 열 차이의 절댓값이 같은지 (즉, 같은 대각선에 위치하는지)

이 세 조건 중 하나라도 만족하면 해당 위치에는 퀸을 놓을 수 없다고 판단한다. 이 과정을 반복하다가 배치한 퀸의 개수(cnt)가 n이 되면, 이는 n개의 퀸을 모두 유효하게 배치한 경우이므로 현재 좌표 목록을 결과로 저장한다.
이후에는 백트래킹을 위해 가장 최근에 추가한 좌표를 제거하고, 같은 행에서 다음 열 위치에 대한 탐색을 계속 진행한다.

모든 탐색이 끝난 뒤에는, 저장된 좌표 형태의 해답을 각 행마다 "."과 "Q"로 구성된 문자열 형태의 보드 표현으로 변환하여 반환한다.

 

 

[풀이 2] Backtracking + Optimization

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        board = [-1] * n # board[row] = col

        cols = set()
        diag1 = set() # row - col
        diag2= set() # row + col

        def dfs(row):
            if row == n:
                res.append(
                    ["." * board[i] + "Q" + "." * (n - board[i] - 1) for i in range(n)]
                )
                return
            
            for col in range(n):
                if col in cols or (row - col) in diag1 or (row + col) in diag2:
                    continue

                board[row] = col
                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)

                dfs(row + 1)

                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)
        
        dfs(0)
        
        return res

첫 번째 풀이를 살펴보면, 충돌 여부를 판단하기 위해 매번 기존에 배치된 모든 퀸을 순회하며 검사를 수행한다. 이 과정에서 다음과 같은 의문을 가질 수 있다.

• 매번 모든 퀸을 순회하지 않고, 더 빠르게 충돌 여부를 판단할 수는 없을까?
• DFS 구조상 각 퀸은 항상 서로 다른 행(row)에 놓이는데, 행 비교가 필요한가?
• 대각선 충돌을 보다 효율적으로 판별할 수 있는 방법은 없을까?

이러한 관찰을 바탕으로, 퀸의 충돌 여부를 O(1)에 판단하기 위해 set 자료구조를 활용할 수 있다.

우선 DFS는 항상 다음 행(row)으로만 진행되므로, 같은 행에 퀸이 배치되는 경우는 애초에 발생하지 않는다. 따라서 충돌 검사에서는 열(col)과 두 방향의 대각선만 고려하면 된다.

열 충돌의 경우, 기존처럼 모든 퀸의 열 좌표를 순회하며 비교하는 대신 이미 사용된 열을 set에 저장해 두고, 현재 열이 해당 set에 존재하는지만 확인하면 된다. 이렇게 하면 열 충돌 여부를 O(1)에 판단할 수 있다.

대각선 충돌 역시 동일한 방식으로 최적화할 수 있다. 두 퀸이 기울기 +1인 대각선에 위치한다는 것은 row1 − row2 = col1 − col2이므로 row1 − col1 = row2 − col2, 즉 row - col가 같은 값을 가진다는 것을​ 의미하고, 기울기 -1인 대각선에 위치한다는 것은

row1 − row2 = -col1 + col2이므로 row1 + col1 = row2 + col2, 즉 row + col가 같은 값을 가진다는 것을​ 의미한다.​ 따라서 각각의 대각선을 row - col, row + col 값으로 표현하고, 이미 사용된 값을 set에 저장해 두면 대각선 충돌 여부 역시 O(1)에 확인할 수 있다.

마지막으로, 좌표를 문자열 형태의 보드로 변환하는 과정도 단순화할 수 있다. 각 행에 배치된 열 번호를 board[row] = col 형태로 저장하면, 결과 변환 시 각 행에 대해 "." * board[row] + "Q" + "." * (n - board[row] - 1)을 바로 생성할 수 있어 추가적인 좌표 순회가 필요하지 않다.

 

⏱️ 시간복잡도

DFS를 n번 반복하며 각 행마다 같은 열에 퀸이 겹치지 않도록 선택하기 때문에, 각 행에서 선택 가능한 열의 수가 점점 줄어든다. 이 구조는 순열(permutation) 탐색과 유사하며, 최악의 경우 O(n!)의 시간복잡도를 가진다.

 

🧠 공간복잡도

set과 board는 각각 최대 n 크기이지만 최종 결과를 저장하는 res는 n × n 크기의 보드 배열을 모든 경우에 대해 저장하므로, 전체 공간복잡도는 O(n²)이다.