BOJ: #3344. N-Queen

DoHn·2025년 4월 15일

python 구현 백준 백준 플레

Baekjoon

목록 보기

2/3

문제

#3344. N-Queen

$N$ 이 주어졌을 때, $N \times N$ 보드에 $N$ 개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 한 가지 경우를 출력하는 프로그램을 작성하시오.

첫째 줄에 $N$ 이 주어진다. $N$ 은 $8,26,213,2012,99991,99999$ 중 하나이다.

접근 방식

먼저, 또 다른 N-Queen 문제(#9663)에서는 백트래킹을 이용해 $N$ 일 때 나올 수 있는 해의 모든 경우의 수를 출력하였다. 해당 코드에서 첫 해를 구한 직후 바로 탈출하면 되지 않을까?

def solution(n: int, check: dict, row: int = 0) -> int:
    if n == row: return True
    for col in range(n):
        # 놓을 수 있는 공간에 말 놓기
        if check["c"][col] and check["u"][row+col] and check["d"][row-col+n-1]:
            check["c"][col] = check["u"][row+col] = check["d"][row-col+n-1] = False
            if solution(n, check, row + 1):
                print(col + 1)
                return True
            check["c"][col] = check["u"][row+col] = check["d"][row-col+n-1] = True
    return False

if __name__ == "__main__":
    N = 8
    check = {
        "c": [True]*N,
        "u": [True]*(N*2),
        "d": [True]*(N*2),
    }
    solution(N, check)

작은 숫자의 경우 빠르게 출력되는 반면, $216$ 과 같은 큰 숫자는 출력되는데 오랜 시간이 소요된다.

따라서 해당 접근 방식은 잘못되었다.

규칙 찾기

퀸을 어떤식으로 두어야 서로 공격할 수 없을까? $N=4$ 인 경우부터 확인해보자.

1. N이 4일 때 (짝수일 때)

$N=4$ 일 때 둘 수 있는 배치는 총 두 가지이다.

□ □ ■ □ ■ □ □ □ □ □ □ ■ □ ■ □ □	□ ■ □ □ □ □ □ ■ ■ □ □ □ □ □ ■ □

여기서 두 번째 배치를 보면, 첫 번째 행부터 $2,4$ , 즉 짝수 칸에 배치하고, 그 이후부터는 $1$ 부터 홀수 칸에 배치한다.

아래 검증 코드를 통해 확인해보자.

# 검증 코드
def check_queen(board: list):
    N = len(board)
    check = {
        "c": [True]*N,
        "u": [True]*(N*2),
        "d": [True]*(N*2),
    }
    for row in range(len(board)):
        if check["c"][board[row]-1] and check["u"][row+board[row]-1] and check["d"][row-board[row]+N-2]:
            check["c"][board[row]-1] = check["u"][row+board[row]-1] = check["d"][row-board[row]+N-2] = False
        else:
            return False
    return True

def solution(n: int) -> int:
    board = []
    # 위쪽부터 짝수로 채우기
    for i in range(2, n + 1, 2):
        board.append(i)
    # 그 이후 홀수로 채우기
    for i in range(1, n + 1, 2):
        board.append(i)
    return board
    
for n in [4, 5, 6, 7, 8, 9, 10]:
    print(f"{n}의 경우:", solution(n), "✅" if check_queen(solution(n)) else "❌")

Output:
4의 경우: [2, 4, 1, 3] ✅
5의 경우: [2, 4, 1, 3, 5] ✅
6의 경우: [2, 4, 6, 1, 3, 5] ✅
7의 경우: [2, 4, 6, 1, 3, 5, 7] ✅
8의 경우: [2, 4, 6, 8, 1, 3, 5, 7] ❌
9의 경우: [2, 4, 6, 8, 1, 3, 5, 7, 9] ❌
10의 경우: [2, 4, 6, 8, 10, 1, 3, 5, 7, 9] ✅

대부분의 짝수, 홀수에서는 정상적으로 동작하지만, $8,9,14,15,26,27$ 등의 숫자에서 반례가 등장한다.

위 숫자들의 공통점은 $6k+2, 6k+3$ 으로 표현된다는 것이다.

해당 숫자들에 대한 규칙도 찾아보도록 하자.

2. N이 6k+2일 때

위 그림을 보면 알 수 있듯이, 체스판 절반 아래쪽 부분이 모두 위쪽 퀸에게 공격받는 모습을 볼 수 있다.

이를 해결하기 위해서, 표시된 빨간색 및 파란색 영역을 제외하고 퀸을 배치했을 때, 서로 공격하지 않도록 해야한다.

위쪽 퀸들의 공격 경로를 빨간색과 파란색 칸으로 표시해 나타내면 다음과 같다.

빨간색 네모칸은 대각선 왼쪽으로 공격하는 경로, 파란색 네모칸은 대각선 오른쪽으로 공격하는 경로, 빨간색 X 표시는 직선 경로를 뜻한다.

여기서 가장 경우의 수가 적은 7번 열부터 시작해본다.

첫 번째 퀸	두 번째 퀸	세 번째 퀸
		3열에 퀸을 놓을 수 없으므로 불가능

$(8,7)$ 에는 퀸을 둘 수 없다.

다음으로, $(7,7)$ 을 확인해보겠다.

첫 번째 퀸	두 번째 퀸	세 번째 퀸	네 번째 퀸

$(7,7)$ 에 퀸을 둘 경우, 위와 같이 배치가 가능하다. 이제 위 배치에서 규칙성을 찾아보자.

$5$ 는 $3$
$6$ 은 $1$
$7$ 은 $7$
$8$ 은 $5$

사실 이거 하나만 봐서는 규칙성을 볼 수가 없다. $N=14$ 인 경우도 봐보자.

여기서 규칙성을 찾을 수 있다. 위쪽 행을 [2, 4, 6, 8, 10, 12, 14]와 같이 짝수 칸으로 채운 후 아래쪽 행을 채울 때, [3, 1] 배열로 시작한다는 것을 알 수 있다. 이후 7부터 홀수 열을 순서대로 채우게 되고, 맨 마지막 행은 5열에 퀸이 놓이게 된다.

이를 코드로 구현하면 다음과 같다.

def solution(n: int) -> list:
    board = []
    for i in range(2, n + 1, 2):
        board.append(i)
    if n % 6 == 2:
        board.append(3)
        board.append(1)
        for i in range(7, n + 1, 2):
            board.append(i)
        board.append(5)
    else:
        for i in range(1, n + 1, 2):
            board.append(i)
    return board

for n in [8, 14, 20, 26]:
    print(f"{n:2d}의 경우:", solution(n), "✅" if check_queen(solution(n)) else "❌")

Output:
 8의 경우: [2, 4, 6, 8, 3, 1, 7, 5] ✅
14의 경우: [2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5] ✅
20의 경우: [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 9, 11, 13, 15, 17, 19, 5] ✅
26의 경우: [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 3, 1, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 5] ✅

완벽하다.

3. N이 6k+3일 때

이제 $6k+3$ 일 때의 규칙을 찾아보자. 이거는 도무지 머리로 규칙이 안떠올라서 전체 경우의 수를 다 출력해두고 괜찮아 보이는 배열을 선택하였다..

위쪽 행은 짝수 열에만, 아래쪽 행은 홀수 열에만 배치한다는 점은 동일하다.

□ □ □ ■ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ ■ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ ■ ■ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ □ □ □

위 배치를 보면, $4$ 부터 시작해서 두 칸씩 건너뛰어 $2$ 까지, 그리고 아래쪽은 $5$ 부터 시작해서 두 칸씩 건너뛰어 $3$ 까지 순서대로 배치하는 것을 알 수 있다.

def solution(n: int) -> list:
    board = []
    if n % 6 == 3:
        for i in range(4, n + 1, 2):
            board.append(i)
        board.append(2)
        for i in range(5, n + 1, 2):
            board.append(i)
        board.append(1)
        board.append(3) 
    else:
        for i in range(2, n + 1, 2):
            board.append(i)
        if n % 6 == 2:
            board.append(3)
            board.append(1)
            for i in range(7, n + 1, 2):
                board.append(i)
            board.append(5)
        else:
            for i in range(1, n + 1, 2):
                board.append(i)
    return board

for n in [9, 15, 21, 27]:
    print(f"{n:2d}의 경우:", solution(n), "✅" if check_queen(solution(n)) else "❌")

Output:
 9의 경우: [4, 6, 8, 2, 5, 7, 9, 1, 3] ✅
15의 경우: [4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3] ✅
21의 경우: [4, 6, 8, 10, 12, 14, 16, 18, 20, 2, 5, 7, 9, 11, 13, 15, 17, 19, 21, 1, 3] ✅
27의 경우: [4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 2, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 1, 3] ✅