[항해 99 챌린지] N-queen 문제

 

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

 

이 문제는 브루트포스로 풀기엔 시간복잡도가 기하급수적으로 늘어나는 아이이다.

따라서 백트래킹으로 문제를 풀게 되는데, 일단 문제 해설을 위해 두가지 경우에 대해 전부 이야기한다.

 

지문 해설

queen은 상하좌우, 대각선 8방향으로 움직일 수 있는 체스말이며, 이를 N*N 체스판에 N개를 서로 공격할수 없게 올리는 경우를 의미한다.

 

위와 같이 둘 경우 X 표시인 경우 다른 퀸을 놓을 수 없다.

이렇게 배치되어야지 nQueen 문제를 해결했다 볼 수 있다.

브루트포스

아래 코드는 본인이 직접 고안해낸 방법은 아니고, 제공받은 방법에 본인 나름의 설명을 더한 것이다.

일단, 퀸의 위치들을 굳이 2차원배열로 저장할 필요가 없다. 

1차원 배열 내에 각 원소에다가 몇 열에 퀸이 위치하는지 적어주면 된다. 예를 들면 아래와 같은 경우

[0,2,3,1]

[0,0] [1,2] [2,3] [3,1] 이렇게 네 군데에 퀸이 배치되었다 볼 수 있다.

 

그리고 이걸 순열을 통해서 N개의 퀸이 다 배치되는 경우를 만들어준다.

* 아래 소스는 순열을 사용했기 때문에 중복되는 원소값이 없어서 가로세로 겹침이 없다 (0,0) (1,0) 같은 경우가 나올 수 없다*

itertools.permutations는 행과 열이 일대일 대응되어 순열을 생성하므로, 가로(행)나 세로(열)에 겹치는 좌표가 생기지 않습니다.

 

그리고 각 배치되는 경우마다, 퀸이 서로를 공격할 수 없는지 파악한다.

 

이 때 해당 배치에 있는 퀸들 중 두개씩 뽑는 경우를 모두 돌아 서로가 공격할 수 있는지 없는지 파악하는 것이다.

위 순열 덕분에(?) 대각선만 비교하면 되기 때문에 행과 행끼리, 열과 열끼리의 차의 절대값이 같은지 확인하면 된다.

0,0	0,1
1,0	1,1

위 예시에선 대각선이 2개가 나오는데, [0,0] [1,1] 의 경우와 [0,1] [1,0]을 비교해보면

[0,0] [1,1] -> 행의 차: 1, 열의 차:1 

[0,1] [1,0]-> 행의 차: 1, 열의 차:1 

이렇게 규칙이 도는걸 확인해 볼 수 있다.

 

이를 통해 퀸이 서로를 공격할 수 없을 때마다 count를 늘려주면 된다.

다만.. 이렇게 구현할 경우 처음에 순열로 생성하는 경우의 수도 만많찮고... 거기에 N^2의 연산도 해야하니 당연히 시간초과가 난다.. ㅠ

from itertools import  permutations

N = int(input())

def is_valid(T):
  for i in range(N):
    for j in range(i + 1, N + 1):
      if(abs(T[i] - T[j]) == abs(i-j)):
        return False
  return True

for perm in permutations(range(N)):
  if is_valid(perm):
    count +=1

print(count)

 

백트래킹

위 시간초과의 경우 다른방법으로 해결할 수 있는데, 백트래킹이라고 한다. 모든 경우의 수를 시도하되, 안될경우 되돌리는 방법이다.

표현상 되돌린다고 했으나, 막상 코드를 짤땐 애초에 재귀를 탈 때 안될만한 경로를 배제하는 식으로 만들면 된다.

현재 상태에서 가능한 모든 선택을 시도한 뒤, 그 선택이 잘못된 경우에는 "되돌려"서 다른 선택을 시도하는 방법입니다.

 

이 방법을 쓸 때는 조건을 재는 방법을 다르게 가야한다. 순열생성시 가로 세로의 경우를 바로 배제하는데, 그게 아니라 전부 다 들어가도록 해야하기 때문이다.

 

열 같은 경우는 재귀로 다음 퀸을 놓을 때 한칸씩 민 상태에서 놓으면 되기 때문에 굳이 검사할 필요가 없다.

행 같은 경우는 배열 하나를 놓아 해당 행에 이미 놓여져 있는 아이인지 확인한다.

대각선의 경우는 아래 표를 참고해서 규칙을 작성하면 된다, 왼쪽 대각선의 경우는 차, 오른쪽 대각선의 경우는 합을 기준으로 구분한다.

대신, 음의정수가 나올 수 있으므로 n을 항상 더해서 양의정수가 나올수 있도록 만들어준다. 

* 본인은 왼쪽 대각선 계산식을 잘못 써서 오답이 나왔었다... 손으로 최소한의 경우는 미리 그려보는 습관을 가지자 ㅜㅜ *

(차: 0) (합: 0)	(차: 1) (합: 1)	(차: 2) (합: 2)	(차: 3) (합: 3)
(차: -1) (합: 1)	(차: 0) (합: 2)	(차: 1) (합: 3)	(차: 2) (합: 4)
(차: -2) (합: 2)	(차: -1) (합: 3)	(차: 0) (합: 4)	(차: 1) (합: 5)
(차: -3) (합: 3)	(차: -2) (합: 4)	(차: -1) (합: 5)	(차: 0) (합: 6)

 

0행애 미리 퀸을 넣어두는 8가지에서 -> 다음 행에 퀸을 넣는 8가지를 타는데... 그 와중에 애초에 성립할 수 없는 경우는 재귀에서 배제하는 형식이다.

n = int(input())
cnt = 0
visted1 = [0 for _ in range(0, n + 1)] #행
cross1 = [0 for _ in range(0, (n + 1) * 2)] #왼대각선
cross2 = [0 for _ in range(0, (n + 1) * 2)] #오른대각선
def queen(i,j,q):
  global cnt
  # 대각선조건
  if(visted1[j] == 0 and cross1[j-i+n] == 0 and cross2[i+j] == 0):
    q += 1
    if(q == n): 
      cnt += 1
    visted1[j] = 1
    cross1[j-i+n] = 1
    cross2[i+j] = 1
    # 다음 녀석들 지정하기 - 다음 열고정, 행만 변경
    if(i + 1 < n): 
      for nx in range(0, n):
        queen(i+1, nx, q)
    # 모든가지 탐색 후 다음께 기능하도록 초기화
    visted1[j] = 0
    cross1[j-i+n] = 0
    cross2[i+j] = 04    

for j in range(0,n):
  queen(0, j, 0);

print(cnt)

 

queen 아이콘 제작자: rizal2109 - Flaticon

X 아이콘 제작자: prinda895 - Flaticon