boj-9663(N-Queen)

백트래킹 알고리즘의 심화버젼...
백트래킹은 여러 케이스를 다 고려하여서, 정답이 되는 것을 찾기에 알맞는 알고리즘이다.
앞 서 N과 M에 대해서는, 알맞는 수 를 찾기보다는 그냥 맞춰서 출력을 하는 그런 방식으로 쓰였다.
더 나아가서 N-Queen은 알맞는 위치를 수학적으로 고려하여, 세는 그런 문제가 되겠다.

혼자서 생각하기에는 너무 어려워서 역시나, 짖는개님의 아티클을 참고하여 해결해보았다.

Queen의 이동 방법

---

퀸은 상, 하, 좌, 우, 대각선 모든 방향으로 다 이동할 수 있다.
그렇기에 퀸들을 놓기 위해서는 제한해야하는 케이스를 몇가지 생각할 수 있다.

• 퀸은 같은 행에는 놓여질 수 없다
• 퀸은 같은 열에는 놓여질 수 없다
• 퀸은 대각선 방향으로는 놓여질 수 없다

그렇기에 이 세가지 조건에 부합하는 케이스에 맞는 자리에 '퀸'들을 배치할 수 있는 것이다.

알고리즘 구성

---

퀸은 같은 행에 존재할 수 없으므로, 각 행에 대해서 퀸이 놓여질 자리를 구분할 필요는 없지만,
같은 열과, 대각선 방향으로의 문제를 고려해야 한다.

같은 열을 구분하는 방법은 간단하다
코드에서 2차원 배열로 구분한, N x N 정사각형이기에 좌표들이 [x][y]라고 한다면
y값이 같으면, 같은 열에 존재한다고 생각할 수 있다.

그리고 다음은 대각선들에 퀸이 올 수 있는지를 판단하는, 대각선의 문제다

대각선은 두가지 종류의 대각선이 생길 수 있는데,
첫번째는 오른쪽 위로 향하는 대각선
또 하나는 오른쪽 아래로 향하는 대각선 이다.

앞서 풀었던 백트래킹 문제와 같이,
isused배열을 이용하여 위의 조건에 맞춰서, 그 자리가 이용이 되었는지 여부를 판단하여 재귀로 문제를 해결해나가면 되겠다.

풀어보자

---

일단 세가지 배열을 만들어 놓아야한다.

• isused_y = [False] * N 열의 위치관계에 대한 배열
• isused_x_pl_y = [False] * (2*N-1) 오른쪽 위로 향하는 대각선에서의 위치관계에 대한 배열
• isused_x_mi_y = [False] * (2*N-1) 오른쪽 아래로 향하는 대각선에서의 위치관계에 대한 배열

만약 N = 4 라면, 만들어지는 정사각형은 인덱스가

	$j=0$	$j=1$	$j=2$	$j=3$
$i=0$	$[0 , 0]$	$[0 , 1]$	$[0 , 2]$	$[0 , 3]$
$i=1$	$[1 , 0]$	$[1 , 1]$	$[1 , 2]$	$[1 , 3]$
$i=2$	$[2 , 0]$	$[2 , 1]$	$[2 , 2]$	$[2 , 3]$
$i=3$	$[3 , 0]$	$[3 , 1]$	$[3 , 2]$	$[3 , 3]$

이런식으로 2차원배열 형태의 인덱스로 표현 가능하다.

1. 같은 열에 퀸이 존재 하는지는 2차원 배열에서 두번째 요소($j$)가 같은지만 확인한면 된다.

2. 오른쪽 위로 향하는 대각선에 대해서는 인덱스의 두 합($i+j$)이 같은 애들을 한 선 위에 있다라고 생각할 수 있다.
   예를 들어, $[1,0]$ 과 $[0,1]$ 은 합이 1인 선 위에 있는 것으로 생각할 수 있고,
   $[2,0]$ 과 $[1,1]$,$[0,2]$ 또한 합이 2인 선 위에 있는 것으로 생각할 수 있다.

3. 오른쪽 아래로 향하는 대각선에 대한 정보는 인덱스의 차($i-j$)가 같은 애들이 한 선 위에 있다라고 생각할 수 있다.
   예를 들어, $[0,2]$ 와 $[1,3]$은 차이가 2로 같아서, 한 선위에 있는 것으로 생각할 수 있고,
   $[0,1]$ 과 $[1,2]$ , $[2,3]$ 은 차이가 1로 같아, 한 선위에 있는 것으로 생각할 수 있다.
   하지만 이런식으로, 인식하게 되면 서로 차를 구했을 때 음수가 나올 수 있기에 실제로 구성할 때는 x-y+N+1 로 구성해주기로 하자.
   그렇게 되면 맨위에 오른쪽 아래로 내려오는 선이 0으로 인식이 될 것이니까.

---

코드를 구성해보자

• 변수
  N = 문제에서 입력을 받는 수
  cnt = 퀸이 놓아질 수 있는 케이스를 세는 변수
  isused_y = 같은 열에 있는지 확인하기 위한 배열
  isused_x_pl_y = $(x+y)$ 오른쪽 위로 가는 대각선 사용에 대한 배열
  isused_x_mi_y = $(x-y)$ 오른쪽 아래로 가는 대각선 사용에 대한 배열
  
  

• 함수 구성
  함수 안에서 변수 cnt를 전역 변수로 사용하여, 바깥 쪽에서 변경이 가능하도록 선언해주고, 재귀를 이용하여 점점 늘려나가며, 퀸을 다 놓으면 cnt를 하나 늘려준다.

def func(cur):
    global cnt
    if cur == N: 
        cnt += 1
        return
    for i in range(N):
        if isused_y[i] or isused_x_pl_y[i+cur] or isused_x_mi_y[cur-i+N-1]:
            continue
        isused_y[i] = True
        isused_x_pl_y[i+cur] = True
        isused_x_mi_y[cur-i+N-1] = True
        func(cur+1)
        isused_y[i] = False
        isused_x_pl_y[i+cur] = False
        isused_x_mi_y[cur-i+N-1] = False

반복을 시행하면서, 조건을 통해 그 자리에 놓아도 될지 안될지를 판단한다

if isused_y[i] or isused_x_pl_y[i+cur] or isused_x_mi_y[cur-i+N-1]:

만약 하나라도 놓여져있다면, continue를 통해서 아래 코드를 점프한다.


아니라면, 그 인덱스를 True로 만들어서 열, 대각선에 이미 사용되고 있다를 명시해주고
다음 재귀로 넘어간다.


그리고 나서는 이제 사용이 완료되면, 해당 인덱스들을 다 False로 바꾸어줘서 사용하지않음을 명시해준다.

---

결론

앞서 풀었던, 해당하는 수열을 다 조사하는 것과 마찬가지로 백트래킹 알고리즘을 이용해서 풀어봤는데, 정말 사람들은 똑똑하구나 생각하게 되었다.
어느 정도 감은 잡혀가지만, 이 백트래킹 알고리즘에서 중요한건 과연 해를 어떤식으로 판단할 것인가가 제일 중요한 것 같다.
이 N-Queen 문제도 해를 저런식으로 판단하는 것을 바로 생각해내는건 처음 접하는 개발자들에게는 많이 힘들 것 같다.
백트래킹 문제들의 유형을 보면서, 다른 사람들의 코드를 많이 참고하여서 해를 판단하는 방법에 대해 고민하고 또 고민해야 할 것 같다.

아, 그리고 참 python3 로 제출하면 시간 초과 난다.
pypy3로 제출하자