[Baekjoon Online Judge] 백준 9663번 N-Queen(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 9663번 N-Queen

(Python)

(글쓴날 : 2020.04.04)

 

---

* Baekjoon Online Judge, 백준 9663번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 9663번 N-Queen

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/9663

9663번: N-Queen

---

2) 풀이 과정

N X N 크기의 체스판에 서로 겹치지 않게 N개의 퀸을 놓을 수 있는 경우의 수를 출력하는 문제이며,

N-Queen 문제라고 불리는, 백트래킹 알고리즘의 가장 대표적인 문제입니다.

 

저의 경우, 정말 아쉽게도 시간 복잡도를 낮추는 방법을 제 스스로 도저히 구현하지 못하겠기에, 다른 분의 방식을 참고하여 문제를 해결했습니다.

 

처음에 제가 생각했던 로직은 DFS를 기본으로 퀸을 체스판에 놓기 전 겹치는 퀸이 있는지 상하좌우, 대각선 전부 체크해가며 해결하는 방식이었고, 이 체크 방법으로 푼 결과 시간 초과가 나왔습니다.

 

이를 해결할 수 있는 방법은 다음과 같습니다.

어차피 "N"개의 퀸이 N X N 크기의 체스판에 놓여야 하므로, 퀸들이 각 행마다 반드시 1개씩 존재해야 하고 따라서 행, 즉, 좌우는 확인할 필요가 없었습니다.

그렇다면, 확인해야 할 남은 방향은 열기준인 상, 하와 대각선인데 열의 경우 길이가 N인 1차원 배열을 만들어 체크를 해주면 되고,

대각선의 경우, 퀸을 기준으로 ↗, ↙ 이 두 가지 방향은 현재 인덱스의 합이 해당 대각선 방향 각각의 인덱스의 합들과 같다는 규칙이 있었습니다.

(체스판에 직접 인덱스를 매겨서 더해보시면 이해가 쉽습니다. ex) (0,2) = (1,1) = (2,0) )

따라서 2차원 배열을 탐색해가며 겹치는 퀸을 체크하는 것이 아닌 길이가 N * 2 -1인 1차원 배열로 체크가 가능해집니다.

나머지 ↖, ↘ 이 두 방향의 경우도 똑같은 원리로 인덱스 제어 변수가 i, j라고 쳤을 때 i-j+N-1이라는 규칙이 성립합니다.

 

이 방법을 적용해 푼 결과 훨씬 더 효율적인 탐색이 가능했고, 결국 문제를 해결했습니다.

다만, Python 3의 경우 이 방식을 적용해도 시간 초과가 발생하며, PyPy3로 제출해야 정답 처리가 됩니다.

아무래도, 백트래킹 알고리즘 분야는 Python으로 풀지 않는 것이 최선일 듯합니다.

 

* 참고 블로그 : https://rebas.kr/761

---

3) 코드

 

* Python 코드(PyPy3)

import sys
input = sys.stdin.readline
 
 
def DFS(i):
    global N, col, slash, backSlash, case
    if i == N:
        case += 1
        return
    for j in range(N):
        if not (col[j] or slash[i + j] or backSlash[i - j + N - 1]):
            col[j] = slash[i + j] = backSlash[i - j + N - 1] = True
            DFS(i + 1)
            col[j] = slash[i + j] = backSlash[i - j + N - 1] = False
 
 
N = int(input())
col, slash, backSlash = [False] * N, [False] * (2 * N - 1), [False] * (2 * N - 1)
case = 0
 
DFS(0)
 
print(case)

---