[hard] 51. N-Queens

문제

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

---

풀이방법

퀸이 갈 수 있는 방향은 가로(↔), 세로(↕), 대각선(↗,↘) 인데 이때 갈 수 있는 방향에 다른 퀸은 없어야 한다.
이 규칙을 만족하면서 모든 행에 퀸을 배치할 때, 가능한 모든 퍼즐 결과를 출력하면 된다.
각 행, 열, 대각선에는 하나의 퀸만 배치되어야 한다. 그래서 이미 퀸이 배치되어있는 열, 대각선을 각각의 리스트에 저장해놓아야 한다.
열을 저장하는 건 간단한데 대각선은 어떻게 저장해야 하나 싶었는데
아래 표를 보면 row-col 이 동일하면 같은 아랫방향 대각선, row+col 이 동일하면 같은 윗방향 대각선이라는 걸 알 수 있다.

0,0	0,1	0,2
1,0	1,1	1,2
2,0	2,1	2,2

각 행마다 backtrack 함수를 실행하는데, 이 때 각 열에 퀸을 배치할 수 있는지 체크하고 가능하면 퍼즐의 해당 위치에 퀸을 배치하면 된다.
backtrack 함수가 마지막 행에 도달했다면 모든 행에 퀸을 배치할 수 있었다는 의미이므로 정답결과 중 하나가 된다.
시간복잡도는 O(n!), 공간복잡도는 O(n^2) 인 것 같다.(헷갈림...)

반응형

---

코드

class Solution:
    def solveNQueens(self, N: int) -> List[List[str]]:
        result = []
        process = [["."]*N for row in range(N)]
        cols = []
        posdiag = []
        negdiag = []
        
        def backtrack(row, col, process):
            process[row][col] = "Q"
            if row == N-1:
                out = ["".join(p) for p in process]
                result.append(out)
                process[row][col] = "."
                return
            cols.append(col)
            posdiag.append(row-col)
            negdiag.append(row+col)
            
            for newcol in range(N):
                if newcol in cols:
                    continue
                if row+1-newcol in posdiag:
                    continue
                if row+1+newcol in negdiag:
                    continue
                backtrack(row+1, newcol, process)
            
            process[row][col] = "."
            cols.remove(col)
            posdiag.remove(row-col)
            negdiag.remove(row+col)            
            
        for col in range(N):
            backtrack(0, col, process)
            
        return result