[Python] Baekjoon 9663 N-Queen 풀이

크기가 N x N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓을 수 있는 방법의 수를 구하라
(주어지는 N은 1 ≤ N < 15 의 값을 가짐)

 

접근 방식

 

체스의 퀸은 상하좌우와 모든 대각선 방향으로 거리 제한없이 공격이 가능하다.

따라서 퀸을 배치한 뒤, 해당 위치에 따라 배치할 수 없는 구역을 설정하고

다음 행에 퀸을 배치하는 방식으로 모든 퀸을 공격할 수 없도록 배치하는

모든 경우의 수를 구한다.

 

 

 

<배치 금지 구역 설정 방식>

1. 행마다 하나의 퀸만 배치함으로써 좌우에 겹치는 퀸이 없도록 설정
2. 퀸을 배치했을 때, 배치한 위치를 기준으로 같은 열에 퀸을 배치하지 못하도록 설정
3. 배치한 위치를 기준으로 양 대각 방향에 퀸을 배치하지 못하도록 설정

(행 기준 위에서 아래 방향으로 퀸을 하나씩 배치하여 위쪽 행에는 배치 금지 구역을 설정하지 않음)

 

구현 코드

def queen(i, n, lst):
    global rst

    if i == n - 1:
        rst += lst[i].count(0)
        return

    for x in range(n):
        if lst[i][x] == 0:
            t, tmp = 0, []
            while i+t < n:
                if lst[i+t][x] == 0:
                    lst[i+t][x] = 1
                    tmp.append([i+t, x])
                if x-t >= 0 and lst[i+t][x-t] == 0:
                    lst[i+t][x-t] = 1
                    tmp.append([i+t, x-t])
                if x+t < n and lst[i+t][x+t] == 0:
                    lst[i+t][x+t] = 1
                    tmp.append([i+t, x+t])
                t += 1
            queen(i+1, n, lst)
            for j, k in tmp:
                lst[j][k] = 0
        else:
            continue

rst = 0
n = int(input())
lst = [[0] * n for _ in range(n)]
queen(0, n, lst)
print(rst)

 

현재 배치하는 퀸의 번호와 퀸이 배치됨에 따라 배치될 수 없는 위치를 저장하는 2차원 배열을 함수의 인자로 보내 모든 경우의 수를 구하는 방식

1. 현재 퀸이 배치될 행의 모든 열을 탐색하며 배치 가능한 구역을 탐색
2. 배치 가능한 구역이 있으면 해당 위치에 퀸을 배치
3. 퀸이 배치된 구역을 기준으로 같은 열과 양 대각 방향을 배치 금지 구역으로 설정
4. 다음 퀸의 번호와 배치 금지 구역을 다시 함수로 전달해 함수 실행
5. 배치한 퀸을 제거한 뒤 배치 금지 구역을 해제하고, 해당 행에 다른 열에 배치 가능 여부 탐색 후, 위의 과정 반복
6. 마지막 행의 퀸을 배치하는 경우에는 해당 열의 배치 금지 구역이 아닌 개수를 결과값에 더하기

이와 같은 과정으로 구현하였으나, 시간이 오래 걸림

- 2차원 배열을 활용한 방식이 오래 걸리는 요소라고 판단

 

구현 방식 2

import sys


def queen(i):
    global n, rst

    if i == n:
        rst += 1
        return

    for x in range(n):
        if not used[x] and not usedUp[i+x] and not usedDown[i-x]:
            used[x] = usedUp[i+x] = usedDown[i-x] = True
            queen(i+1)
            used[x] = usedUp[i+x] = usedDown[i-x] = False


rst = 0
n = int(sys.stdin.readline().rstrip())
lst = [[0] * n for _ in range(n)]
used, usedUp, usedDown = [False] * n, [False] * (2 * n - 1), [False] * (2 * n - 1)
queen(0)
print(rst)

배치 금지 구역을 2차원 배열이 아닌 3개의 1차원 배열을 활용하여 표기하는 방식

퀸 기준 왼쪽 대각선 아래 방향은 (y=x 그래프) 두 좌표의 합(행의 좌표 + 열의 좌표) 과 같음

 

 

 

 

 

 

 

 

 

퀸 기준 오른쪽 대각선 아래 방향은 (y=-x 그래프) 두 좌표의 차(행의 좌표 - 열의 좌표)와 같다.

 

 

 

 

 

 

1. 위의 구현 과정과 같은 방식으로 진행하나 퀸 배치 후, 배치 금지 구역을 계산해 3개의 1차원 배열에 값을 변경
2. 이에 따라 다음 퀸의 배치 구역을 설정하는 방식으로 결과를 구하기

 

---

 

참고 사이트

 

https://velog.io/@kjy2134/%EB%B0%B1%EC%A4%80-9663-N-Queen-%ED%8C%8C%EC%9D%B4%EC%8D%AC

백준 9663 N-Queen : 파이썬

 

백준 9663 N-Queen : 파이썬