[백준] 9663번: N-Queen (python)

9663번: N-Queen

---

문제 )

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

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

 

 

 

입력 :

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

 

 

출력 :

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

 

 

 

 

풀이)

내 컴퓨터로도 약간 13부터는 느리게 나오는데 정답처리를 해줘서

 

왠지 백준 서버가 봐준듯한 느낌이 드는 문제였다.

 

방문처리를 통해 만들 수 있는 모든 경우의 수를 세주었다.

 

def recur(cur):
    global cnt
 
    if cur == n:
        cnt += 1
        return
 
    for i in range(n):
        if visited[cur][i]:
            continue
        
        # 방문처리
        for j in range(n - cur):
            for k in range(6):
                x = cur + di[k] * j
                y = i + dj[k] * j
                if -1 < x < n and -1 < y < n:
                    visited[x][y] += 1
 
        recur(cur + 1)
        
        # 방문처리 초기화
        for j in range(n - cur):
            for k in range(6):
                x = cur + di[k] * j
                y = i + dj[k] * j
                if -1 < x < n and -1 < y < n:
                    visited[x][y] -= 1
 
n = int(input())
visited = [[0] * n for i in range(n)]
 
# 밑으로만 내려가므로 6방 탐색
di = [-1, 1, 0, 0, 1, 1]
dj = [0, 0, -1, 1, -1, 1]
 
cnt = 0
recur(0)
print(cnt)

 

 

위의 방법은 2차원을 이용하여 푸는 방법이고, visited배열에 일일이 지웠다가 썼다가를 반복하기 때문에

시간이 오래 걸린다.

 

n-queen 문제는 잘 알려진 문제라 다른 풀이도 가져와봤다.

 

- 배열을 1차원으로 생각해서 푸는 풀이.

 

체스판에서 퀸이 놓인 열의 위치에 따라 1차원 배열로 만들어 활용. 

ex) n = 4일때  (2, 0, 2, 0)과 같은 식으로 표현

 

이런식으로 표현하게 되면 배열에 같은 숫자가 있게되면 열 위치가 같다는 이야기가 되게 되며,

 

인덱스 번호의 차이가 열 번호의 차이 이면 대각선 상에 있다는 걸 알 수 있다.

 

이를 코드로 표현하면 다음과 같다.

 

def check(cur):
    for i in range(cur):
        if abs(row[cur] - row[i]) == cur - i:
            return False
    return True
 
def recur(cur):
    global cnt
 
    if cur == n:
        cnt += 1
        return
 
    for i in range(n):
        if visited[i]:
            continue
 
        row[cur] = i
        if check(cur):
            visited[i] = 1
            recur(cur + 1)
            visited[i] = 0
 
 
n = int(input())
row = [0] * n
visited = [0] * n
cnt = 0
recur(0)
print(cnt)

 

---

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

9663번: N-Queen