16. 백준 9663 (골드4) : N-Queen _ python풀이 / 브루트포스

문제

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

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

입력

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

출력

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

예제 입력 1 복사

8

예제 출력 1 복사

92

---

 

어떤 문제인지는 앞으로 제목에 적어둘 예정이다.

 

*문제 해석

 백트래킹하면 나오는 기본 문제인 N-Queen 문제다. 퀸이 서로를 공격할 수 없는 경우는 다음과 같다.

1. 행과 열마다 한개의 퀸만 존재한다.

2. 같은 대각선상에 퀸이 존재하지 않는다.

 

'1'을 풀기 위해서는 각 행들을 하나의 리스트로 하고 리스트 별로 인덱스가 겹치지 않게 퀸을 배치하는 식으로 하면 될 것이다.

 

'2'를 풀기 위해서는 퀸 간의 행과 열의 차이가 동일하지 않은 지를 판단해야한다. 동일하다면 정사각형 양 끝에 퀸이 위치했다는 것이고, 그 말은 둘은 대각선에 있는 것이기 때문이다.

 

 

*나의 코드

import sys
input = sys.stdin.readline
 
n = int(input())
 
# 퀸의 공격여부 확인
def attack(x):
    for i in range(x): 
        # 같은 행에 퀸이있거나 대각선에 퀸이 있는 경우 : 1번 경우와 2번 경우
        if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i):
            return True
    return False
 
def dfs(start):
    global result
 
    if start == n: # 마지막까지 탐색했을 경우
        result += 1
    else:
        for i in range(n):
            row[start] = i
            if not attack(start): # 퀸의 위협을 받지 않는다면 다음 탐색
                dfs(start + 1)
 
row = [0] * n # 체스판 생성
result = 0
dfs(0)
 
print(result)

* python3으로 풀이시 시간초과, pypy3사용할 것

*중요한 점

1. 백트래킹 문제 시간초과가 생길경우 pypy3로 컴파일 하기
2. 탐색문제에선 조건을 파악하고 정리하는 것이 중요하다.