Leetcode 51. N-Queens - Python (cf. 백준 9663)

from LeetCode 51

 

Leetcode 51 문제 보기

 

문제 이해하기

n X n 체스판 위에 n개의 queen을 배치하려한다. (1 <= n <= 9)

이 때 각각의 queen들이 서로를 잡을 수 없는 위치에 놓여있도록 체스판 위에 배치할 수 있는 경우에 해당하는 체스판의 모습을 일차원 리스트의 형태로 출력하라.

 

아이디어 구상

체스 말 중 퀸은 가로, 세로, 대각선으로 움직일 수 있다.

따라서 n개의 퀸들은 동일한 가로, 세로, 대각선 상에 놓여있어서는 안된다.

 

그렇다면 가로, 세로, 대각선에 해당하는 set을 만들어, 하나의 퀸을 추가할 때마다 각각의 set에 값을 입력하자.

이 후, 또다른 하나의 퀸을 추가할 때 set에 있는 값은 피해서 배치하도록 구현하면 되겠다.

가로, 세로는 각각 row와 col이 되므로 어렵지 않다. 그러나 대각선은 어떻게 판별해야할까?

 

⬈ 방향의 경우, 하나의 대각선에 대하여 (row + col)의 값들이 일정함을 알 수 있다.

⬊ 방향의 경우, 하나의 대각선에 대하여 (row - col)의 값들이 일정함을 알 수 있다.

따라서 대각선 set을 ⬈ 방향과 ⬊ 방향으로 나누고 구현을 할 수 있겠다.

 

추가적으로 조금만 더 생각해보면, 가로 방향의 set은 굳이 사용하지 않아도 됨을 알 수 있다.

기본적으로 하나의 row에는 하나의 퀸만 배치될 수 있음을 고려한다면, set이 아닌 backtracking 함수의 parameter로 하여 애초에 필터링할 수 있다.

 

풀이

세로 방향과 두 대각선에 대해 set을 선언하자.

이 때 ⬈ 방향은 pos_diag, ⬊ 방향은 neg_diag로 한다.

col, pos_diag, neg_diag = set(), set(), set()

 

또한 가능한 결과 리스트들을 담을 리스트 res를 선언하고, 체스판을 초기화한다.

res = []
board = [["."] * n for i in range(n)]

 

backtrack함수의 base case는 다음과 같다.

만약 탐색하는 row가 n, 즉 마지막 row에 도달했다면 문제의 출력 조건에 맞게 체스판을 res에 담고 return한다.

if r == n:
    possible = ["".join(row) for row in board]
    res.append(possible)
    return

 

backtrack함수의 재귀 부분은 다음과 같다.

각각의 column을 반복문을 통해 탐색하면서 해당 위치에 퀸을 배치가능한지 확인한다.

만약 배치가능하다면 set에 해당 위치를 추가하고 체스판에 퀸을 배치한 후, backtrack()을 진행한다.

for c in range(n):
    if (c in col or
        (r + c) in pos_diag or
        (r - c) in neg_diag):
        continue

    col.add(c)
    pos_diag.add(r + c)
    neg_diag.add(r - c)
    board[r][c] = "Q"
                
    backtrack(r + 1)
                
    col.remove(c)
    pos_diag.remove(r + c)
    neg_diag.remove(r - c)
    board[r][c] = "."

 

전체 코드는 다음과 같다.

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        col, pos_diag, neg_diag = set(), set(), set() # c, (r + c), (r - c)
        res = []
        board = [["."] * n for i in range(n)]
        
        def backtrack(r):
            # base case
            if r == n:
                possible = ["".join(row) for row in board]
                res.append(possible)
                return
            
            for c in range(n):
                # pruning impossible position
                if (c in col or
                    (r + c) in pos_diag or
                    (r - c) in neg_diag):
                    continue
                
                # update sets
                col.add(c)
                pos_diag.add(r + c)
                neg_diag.add(r - c)
                # place queen on board
                board[r][c] = "Q"
                
                backtrack(r + 1)
                
                # initialize sets
                col.remove(c)
                pos_diag.remove(r + c)
                neg_diag.remove(r - c)
                # initialize board
                board[r][c] = "."
                
        backtrack(0)
        return res

 

---

백준 9663번 문제는 위와 같은 문제다.

백준 9663 문제 보기

 

문제 이해하기

output으로 가능한 경우의 수를 출력해야하는 점을 제외하면, 문제는 동일하다.

다만 n의 범위가 1에서 최대 15까지이며, 이로 인해 주어진 제한시간내에 CPython으로 해답을 구하기가 매우 어렵다.

때문에 Pypy3로 코드를 제출했다.

 

아이디어 구상

가능한 경우의 수만 출력하면 되므로, 굳이 board를 가지고 갈 필요가 없다.

 

풀이

전체 코드

n = int(input()) # 1 ≤ N < 15
col, pos_diag, neg_diag = set(), set(), set()  # c, (r + c), (r - c)
res = 0 # possible chessboards

def backtrack(r):
    global res
    # base case
    if r == n:
        res += 1
        return

    for c in range(n):
        # pruning impossible position
        if (c in col or
            (r + c) in pos_diag or
            (r - c) in neg_diag):
            continue

        # update sets
        col.add(c)
        pos_diag.add(r + c)
        neg_diag.add(r - c)

        backtrack(r + 1)

        # initialize sets
        col.remove(c)
        pos_diag.remove(r + c)
        neg_diag.remove(r - c)

backtrack(0)
print(res)

 

---

Leetcode 51. N-Queens

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

 

백준 10974. N-Queen (골드 5)

https://www.acmicpc.net/problem/9663​

 

 

 

 

-문제해결흐름을 간단히 정리한 주관적 포스팅-

 

-부족한 설명이 있다면 부디 조언 부탁드립니다-

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다