[백준] 9663번 N-Queen 해설 및 풀이 (Python)

백준 9663번 N-Queen

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

 

---

 

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

---

 

문제 풀이

 

문제 유형

 

브루트포스 알고리즘

백트래킹

 

풀이 방법 도출

 

문제는 N x N 크기의 체스판에서 N개의 퀸을 서로 공격할 수 없도록 배치하는 방법의 수를 구하는 문제입니다.

퀸은 같은 행과 같은 열과 대각선 방향으로 공격할 수 있습니다.

 

퀸의 공격 방식은 아래와 같습니다.

 

1. 같은 행에 놓을 수 없습니다.
2. 같은 열에 놓을 수 없습니다.
3. 왼쪽 대각선에 놓을 수 없습니다
4. 오른쪽 대각선에 놓을 수 없습니다.

 

따라서 한 행에는 하나의 퀸만 놓을 수 있음을 활용하여 백트래킹을 수행합니다.

 

1. 퀸을 배치할 때, 세 가지 조건을 배열을 사용합니다.
2. 첫 번째로 같은 열에 사용되었는지 확인합니다.
3. 두 번째로 왼쪽 대각선에 사용되었는지 확인합니다.
4. 세 번째로 오른쪽 대각선에 사용되었는지 확인합니다.
5. row == N이 되면 모든 행에 퀸을 배치한 것이므로 경우의 수 증가합니다.
6. 퀸을 배치한 후, 다음 행으로 이동합니다.
7. 백트래킹을 수행하여 퀸을 제거하고 다른 경우 탐색합니다.

시간 복잡도

• O(N)

 

---

문제 풀이 핵심 코드

 

import sys


def n_queens(row):
    """
    백트래킹을 이용해 퀸을 배치하는 함수
    """
    global count
    if row == N:  # 모든 행에 퀸을 배치하면 경우의 수 증가
        count += 1
        return


    for col in range(N):  # 모든 열에 대해 퀸을 배치 시도
        if not col_used[col] and not diag1[row + col] and not diag2[row - col + (N - 1)]:  
            # 현재 위치에 퀸을 놓을 수 있는 경우
            col_used[col] = diag1[row + col] = diag2[row - col + (N - 1)] = True  # 퀸 배치
            n_queens(row + 1)  # 다음 행으로 이동
            col_used[col] = diag1[row + col] = diag2[row - col + (N - 1)] = False  # 백트래킹


N = int(sys.stdin.readline().strip())  # 입력 받기
col_used = [False] * N  # 열(column) 사용 여부 체크
diag1 = [False] * (2 * N - 1)  # 왼쪽 아래 대각선 체크
diag2 = [False] * (2 * N - 1)  # 오른쪽 아래 대각선 체크
count = 0  # 가능한 경우의 수 저장 변수


n_queens(0)  # 첫 번째 행부터 시작
print(count)  # 퀸을 놓는 방법의 수 출력