[Baekjoon] 9663번 : N-Queen (Python, 백트래킹)

[Baekjoon] 9663번 : N-Queen (Python, 백트래킹)

 

목차

 

 

 

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

9663번: N-Queen

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

시간초과 - 방법 1 -  코드 길이 490B (PyPy3 통과)

 

나무위키 - 퀸

 

본 문제는 NxN인 체스판에서 퀸 N개를 놓을 수 있는 가지 수를 찾는 문제다.

이때의 퀸은 좌우 대각선에 대하여 움직일 수 있는 권한이 존재한다.

 

단순히 생각해봐도 그 가지 수는 적을 것으로 예상된다.

그러나 NxN인 체스판에서 N개의 퀸을 놓을 수 있는 방법을 생각해보면 다음과 같은 특징이 있다.

 

1) 한 행에는 1개의 퀸만 놓인다. 이는 한 열에 대해서도 마찬가지이다.

2) 모든 행에 대하여 놓인 퀸의 대각선 상에 놓이지 않는다.

 

이것을 말로 풀어보면 다음과 같이 풀어낼 수 있다.

 

"

행마다 0~n-1의 열에 해당하는 곳으로 이동해보이겠어. (백트래킹)

다만 행마다 위치한 곳은 다른 퀸과 같은 열에 놓이면 안 되고,

대각선 상에도 존재하지 않음을 확인하면서 움직이겠어.

"

 

그럼 여기서 확인하는 작업은 어떻게 할 수 있을까에 대해 고민하게된다.

기준은 row라는 list에 대해 행하는 것이다.

(여기서 row[i] = j에서 i,j는 각각 i행 j열을 의미한다.)

그리고 조건에 부합할 때 DFS로 더 진행이 되고 행이 N이 되는 순간 결과에 부합하니 counting에 들어가고 만약 조건에 부합하지 않느다면 백트래킹에 의해 이전 행으로 되돌아가게 된다.

 

추가로 대각선에 대한 조건 확인을 어떻게 하냐고 물을 수 있다.

아래를 확인해보면 (1,1)을 기준으로 대각선에 해당하는 좌표를 표시해놓았다.

잘 확인해보면 |행-1| = |열-1| = 1임을 확인할 수 있다.

 

(0,0)		(0,2)
	(1,1)
(2,0)		(2,2)

 

(2,2) 기준으로 대각선 좌표를 표시해보았다.

이 역시 잘 확인해보면

1거리에 해당하는 대각선에서는 |행-2| = |열-2| = 1,

2거리에 해당하는 대각선에서는 |행-2| = |열-2| = 2,

임을 확인할 수 있다.

(0,0)				(0,4)
	(1,1)		(1,3)
		(2,2)
	(3,1)		(3,3)
(4,0)				(4,4)

 

이를 사용하여 조건문에 기입하면 not_adj 함수와 같이 나타낼 수 있다.

  

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

def not_adj(x):
    for i in range(x):
        if row[x] == row[i] or abs(row[x] - row[i]) == x-i:
            return False
    return True

def dfs(x):
    global res

    if x == n:
        res += 1
    else:
        for i in range(n):
            row[x] = i
            if not_adj(x):
                dfs(x+1)

n = int(input())
row = [0]*n
res = 0
dfs(0)
print(res)

 

def not_adj(x):
    for i in range(x):
        if row[x] == row[i] or abs(row[x] - row[i]) == x-i:
            return False
    return True

def dfs(x):
    global res

    if x == n:
        res += 1
    else:
        for i in range(n):
            if visit[i]:
                continue
            row[x] = i
            if not_adj(x):
                visit[i] = 1
                dfs(x+1)
                visit[i] = 0

n = int(input())
row = [0]*n
visit = [0]*n
res = 0
dfs(0)
print(res)

 

 

시간 초과 - 방법 2 -  코드 길이 414B (PyPy3 통과)

 

 방법 1에서는 조건부 함수 not_adj를 통해 값을 열과 대각선에 대한 부분에 겹침이 없는지 확인했다.

그러나 열과 왼쪽 위로 가는 대각선, 오른쪽 위로 가는 대각선 3개에 대한 list를 통해서도 해결이 가능하다.

 

https://rebas.kr/761

https://rebas.kr/761

BOJ 9663 · N-Queen

 

위에 보이는 그림과 같이 각 행마다 열에 대한 값들은 크게 n개로 구분이 가능하다.

오른쪽 위로 가는 대각선의 경우 대각에 대한 i와 j의 값을 더하는 것으로 그 구분이 가능하고

왼쪽 위로 가는 대각선의 경우 대각에 대한 i와 j의 값을 빼는 것으로 그 구분이 가능하다.

 

이점을 활용하여 방문 처리에 대한 값으로 문제를 해결할 수 있다.

 

물론 이 방법으로도 시간 초과가 나온다. 

 

N = int(input())
cnt = 0
bd = [False] * N  
diag1 = [False] * (2 * N) 
diag2 = [False] * (2 * N) 

def f(i):    
    if i == N:        
        global cnt;
        cnt += 1
        return
    for j in range(N):
        if not (bd[j] or diag1[i + j] or diag2[i - j]):
            bd[j] = diag1[i + j] = diag2[i - j] = True
            f(i + 1)
            bd[j] = diag1[i + j] = diag2[i - j] = False
f(0)
print(cnt)

 

 

방법 3 -  코드 길이 95B 

 

편법 

 

a = (0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596)
print(a[int(input())])