leetcode 52. N-Queens II

leetcode Monthly Challenge - N-Queens II

N-Queens II - LeetCode

---

문제

leetcode: N-Queen II

문제 풀이

해당 문제 역시 leetcode의 5월 Daily Challenge 문제였다. 문제를 풀이한 후에 난이도가 Hard인 것을 확인했는데, 사실 N-Queen 문제는 워낙 유명하기도 하고 예전에 백준에서 비슷한 문제를 한 번 풀어본 적 있었기 때문에 어렵지 않게 풀이할 수 있었던 것 같다.

 

사실 이 문제는 백트래킹을 이해하고 있다면 구현이 어렵진 않지만, Queen 들을 특정한 자리에 놓을 때 그 자리에 놓는 것이 가능한지 체크하는 로직을 생각해내지 못한다면 약간 어려움을 겪을 수는 있을 것 같았다.

 

내가 생각한 퀸을 놓을 수 있는지 체크하는 로직은 다음과 같다.

def check(board, r, c):
            # 행 체크
            if 1 in board[r]:
                return False
            
            # 열 체크
            for i in range(n):
                if board[i][c]:
                    return False
            
            # 좌상(\) 대각선 체크
            tmpR = 0 if r < c else r - c
            tmpC = 0 if c < r else c - r
            
            while tmpR < n and tmpC < n:
                if board[tmpR][tmpC]:
                    return False
                
                tmpR += 1
                tmpC += 1
            
            # 우상(/) 대각선(기준점보다 좌측) 체크
            tmpR = r
            tmpC = c
            
            while 0 <= tmpR < n and 0 <= tmpC < n:
                if board[tmpR][tmpC]:
                    return False
                
                tmpR += 1
                tmpC -= 1
            
            # 우상(/) 대각선(기준점보다 우측) 체크
            tmpR = r
            tmpC = c
            
            while 0 <= tmpR < n and 0 <= tmpC < n:
                if board[tmpR][tmpC]:
                    return False
                
                tmpR -= 1
                tmpC += 1
            
            return True

체크하는 로직이 너무 복잡하고 가독성이 떨어지는 것이 사실이다. 그래도 설명을 하자면, 백트래킹을 진행하며 특정한 자리마다 퀸을 놓을 수 있는 상태인지 아닌지 체크를 하는 함수 check를 호출하여 체크한다.

 

1. 만약 같은 행에 퀸이 있다면 불가능
2. 만약 같은 열에 퀸이 있다면 불가능
3. 만약 같은 대각선에 퀸이 있다면 불가능

이렇게 총 3가지로 나누어서 체크를 해주었다. 대각선의 경우에는 어떻게 체크를 해주었냐 하면, 좌상 대각선의 경우에는 행과 열 좌표의 차(절댓값)가 항상 같은 대각선 내에서 같기 때문에 그러한 로직으로 처리해주었다.

 

그리고 우상 대각선 그래프의 경우에는 좌측, 우측 따로 나누어 주었는데, 그 이유는 좌측의 경우에는 현재 좌표를 기준으로 행은 +1 만큼, 열은 -1 만큼 이동하며 우측의 경우에는 그 반대로 동작하기 때문이었다.

 

결과적으로 전체 코드를 보면 아래와 같다.

class Solution:
    def totalNQueens(self, n: int) -> int:
        def check(board, r, c):
            if 1 in board[r]:
                return False
            
            for i in range(n):
                if board[i][c]:
                    return False
            
            tmpR = 0 if r < c else r - c
            tmpC = 0 if c < r else c - r
            
            while tmpR < n and tmpC < n:
                if board[tmpR][tmpC]:
                    return False
                
                tmpR += 1
                tmpC += 1
            
            tmpR = r
            tmpC = c
            
            while 0 <= tmpR < n and 0 <= tmpC < n:
                if board[tmpR][tmpC]:
                    return False
                
                tmpR += 1
                tmpC -= 1
            
            tmpR = r
            tmpC = c
            
            while 0 <= tmpR < n and 0 <= tmpC < n:
                if board[tmpR][tmpC]:
                    return False
                
                tmpR -= 1
                tmpC += 1
            
            return True
            
        
        def dfs(cnt, r, c):
            if cnt == n:
                ans[0] += 1
                return

            if c == n:
                r += 1
                c = 0
            
            for i in range(r, n):
                for j in range(n):
                    if i == r and j < c:
                        continue
                    
                    if not check(board, i, j):
                        continue
                    
                    board[i][j] = 1
                    dfs(cnt + 1, i, j + 1)
                    board[i][j] = 0
        
        board = [[0 for _ in range(n)] for _ in range(n)]
        ans = [0]
        
        dfs(0, 0, 0)
        
        return ans[0]
        

결과

leetcode: N-Queen II 제출 결과

제출한 코드의 성능이 좋지 못한 것을 확인할 수 있는데, 그 이유는 아마도 각 퀸을 놓을 때마다 반복적으로 check 함수 내부적으로 for문을 돌기 때문인 것 같다.

 

이를 개선하기 위해선 check 함수를 개선할 필요가 있어 보이며, 그 방법으로는 각 행, 열, 대각선마다 set 자료구조를 통해서 현재 퀸이 있는지 없는지 체크하면 O(1)의 시간 복잡도만에 퀸을 놓을 수 있는지 체크해줄 수 있을 것이다.