[백준] 9663.N-Queen

김규민·2025년 4월 9일

알고리즘 문제풀이

목록 보기

7/13

N-Queen

해결 아이디어

퀸은 가로세로 뿐만 아니라 대각선으로도 공격 가능하다는 사실이 문제의 난이도를 올리는 부분이라고 생각한다.

체스판은 n 크기의 정사각형으로, 만약 퀸이 아니라 룩이었다면 한 줄씩 내려가면서 이전의 룩이 놓여진 열을 제거하는 방식으로 놓을 자리를 찾으면 된다.
퀸은 이에 조건을 추가하여 이전에 놓여진 퀸의 대각선상에 위치하는 열(칸) 또한 제거해야 한다.

이때 필요한 판단이 필요한 갈림길은 크게 2가지라고 생각한다.

이전 퀸의 대각선 위치를 파악하는 방법
놓을 수 없는 칸을 기록하는 방법

이전 퀸의 대각선 위치를 파악하는 방법

직관적인 대각선 파악 방식
대각선을 파악하기 위해 처음 떠올린 생각은 이전 퀸의 좌표로부터 (1, 1), (-1, -1), (1, -1), (-1, 1) 씩 반복해서 n 크기의 체스판을 모두 확인하는 방법이다.
4가지 방향의 대각선에 대해 각각 반복하며 하나씩 체크하기 때문에 직관적이기는 하나 효율적이지 않다는 느낌이 있다.

좌표 공간에서 대각선의 규칙성
두 번째 방법은 스스로 전혀 떠올릴 수 없던 방법이다.
이 방법은 익숙하지 않은 수학적 규칙성을 이용하기 때문에 코드 작성 이후에도 이해는 하지만 납득은 잘 되지 않는다.
(좌표공간에 대해 익숙한 사람들에게는 납득이 쉬운 방법일 수 있다.)
n 크기의 정사각형이 아니라 정수로 이루어진 정사각형의 좌표 공간을 떠올리는 것이 도움이 된다.

좌표 속성의 합
각 대각선에 대응하는 좌표들은 공통된 규칙을 따르게 된다.
왼쪽 위에서부터 오른쪽 아래까지 체스판의 한 칸의 좌표를 (0, 0) ~ (n-1, n-1) 이라고 하자.

왼쪽 위에서 오른쪽 아래(↘) 방향의 대각선 좌표들은 좌표값의 합이 행-열 의 값이 일정한 값을 가지는 점들의 집합이다.
반대로, 오른쪽 위에서 왼쪽 아래(↙) 방향의 대각선 좌표들은 좌표값의 합이 행+열 의 값이 일정한 값을 가지는 점들의 집합이다.

이 특징을 통해 퀸의 위치에서 대각선에 위치한 좌표들을 지정할 수 있다.

결국 대각선에 대응하는 점들을 하나씩 파악하는 것이 아니라 행+열 또는 행-열 값이 일정한 점들을 하나의 대각선으로 묶어서 파악할 수 있는 것이 핵심이다.

체스판	0열	1열	2열
0행	(0,0)	(0,1)	(0,2)
1행	(1,0)	(1,1)	(1,2)
2행	(2,0)	(2,1)	(2,2)
3행	(3,0)	(3,1)	(3,2)

놓을 수 없는 칸을 기록하는 방법

list 등록 후 제거
2차원 list 를 통해 체스판의 칸을 기록하는 방법이 가장 직관적이고 먼저 떠오르는 방법이다.

[[0, 1, 2, 3], 
[0, 1, 2, 3], 
[0, 1, 2, 3]]

이전 퀸에 의해 놓을 수 없는 칸이 추가되면 이후에 해당 칸을 고려하지 않기 위해(효율적인 계산을 위해) 제거할 수 있다.
list 에서 사용할 수 없는 열을 제거하게 되면, 이후의 행에서 퀸을 놓을 수 없는 상황이 되었을 때, 다시 돌이킬 수 없다는 문제가 있다. 제거한 열이 언제 몇개가 제거되었는지 알 수 없기 때문에 list 의 값을 제거하는 방식은 사용할 수 없다.

bool 타입의 list 수정
파악해야 하는 영역이 변하지 않는 조건의 문제에서 boolean 타입의 list 를 통해 데이터의 변경을 기록하는 경우가 많다. 알파벳이나 체스판 등 정해져 있는 영역의 데이터를 파악할 때 유용하다.

앞서 체스판의 대각선에 대해 파악하는 방법을 알아보았다. 대각선의 개수는 대각선의 방향마다 2n-1 개 존재하기 때문에 2n-1 크기의 list 2개를 통해 놓여진 퀸에 의해 사용할 수 없는 대각선을 기록할 수 있다.

대각선의 개수
정사각형에서 대각선은 2개이지만, 정수 좌표 공간에 대각선은 2(2n-1) 개이다.
이미지가 대각선의 개수를 세는 데 도움이 되었으면 한다.

코드

def solve_n_queens(n):
    result = 0
    col_used = [False] * n           # 열 체크
    diag1_used = [False] * (2 * n)   # ↘ 대각선 체크 (row + col)
    diag2_used = [False] * (2 * n)   # ↙ 대각선 체크 (row - col + n)

    def backtrack(row):
        nonlocal result
        if row == n:
            result += 1
            return

        for col in range(n):
            if col_used[col] or diag1_used[row + col] or diag2_used[row - col + n]:
                continue

            # 놓기
            col_used[col] = diag1_used[row + col] = diag2_used[row - col + n] = True
            backtrack(row + 1)
            # 되돌리기
            col_used[col] = diag1_used[row + col] = diag2_used[row - col + n] = False

    backtrack(0)
    return result


# 입력 및 출력
n = int(input())
print(solve_n_queens(n))