BOJ 9663 N-Queen

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

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

문제 : BOJ 9663

📍구현을 위한 시행착오

☝️ 퀸을 놓을 수 없는 곳 모두 표시하기

가장 단순한 생각으로 시작했다.

N * N 크기의 Bool type 2차원 배열을 만들어서
퀸을 놓을 수 없는 곳을 모두 표시하자

백트래킹을 이용한 완전 탐색으로 접근하였다.

2중 for문으로 배열을 순회해서
퀸을 놓을 수 있다면 퀸을 놓는다.

n = 4 인 경우
0 0 0 0     1 0 0 0
0 0 0 0  →  0 0 0 0
0 0 0 0     0 0 0 0
0 0 0 0     0 0 0 0

퀸이 이동할 수 있는 모든 곳의 값을 False로 갱신한 뒤
새로운 리스트에 좌표 튜플을 저장한다.

1 0 0 0     1 1 1 1
0 0 0 0  →  1 1 0 0
0 0 0 0     1 0 1 0
0 0 0 0     1 0 0 1

이후 탐색이 종료되면 좌표 튜플을 가진 리스트를 이용해서
탐색 전 False로 갱신한 곳의 좌표를 다시 True로 바꿔주었다.

1 1 1 1     0 0 0 0
1 1 0 0  →  0 0 0 0
1 0 1 0     0 0 0 0
1 0 0 1     0 0 0 0

결과 : Python3 시간 초과

퀸을 놓고, 이동할 수 있는 모든 좌표를 체크하는 것이 비효율적이라고 판단되어
다른 방법을 구상해 보았다.

✌️ 행과 열, 대각선을 표현하는 방법 생각하기

행과 열

• 첫 행에 퀸을 놓게 되면,
  퀸의 이동 조건에 의해 해당 행에는 더 이상 퀸을 놓을 수 없다.

• 따라서, 2중 for문이 아닌
  col을 순회하기 위한 for문 하나만을 이용하고
  재귀 호출의 깊이를 체크하기 위해 사용한 depth를 row로 하여
  모든 경우의 수를 탐색할 수 있다.
  
  

방문 체크

1. 행과 열

• 행(row)의 경우,
  row의 역할을 하는 depth가 1씩 증가하며 탐색이 진행되기 때문에
  별도로 방문 체크를 해주지 않아도 된다.
  

• 열(col)의 경우,
  index를 col로 하는 배열을 만들어서 방문 체크를 해준다.

visited_col = [0 for _ in range(n)]
# col에 퀸이 위치했을 경우 아래와 같이 방문 체크를 해준다.
# visited_col[col] = 1

2. 대각선
   row와 col을 이용해서 대각선 상의 좌표를 사용할 수 있는지 체크해야 한다.

   대각선의 종류는 두가지로 구분 할 수 있다.
   1️⃣ : 왼쪽 위에서 오른쪽 아래로 향하는 대각선 ➘
   2️⃣ : 왼쪽 아래에서 오른쪽 위로 향하는 대각선 ➚

   • 1️⃣번 대각선의 경우, 열이 증가하면 행도 증가하는 y = x + a 그래프이다.
     따라서 row-col값이 같다는 사실을 확인할 수 있다.

     	0	1	2	3	4	5
     0	( 0 )	(-1)	(-2)	(-3)	(-4)	(-5)
     1	( 1 )	( 0 )	(-1)	(-2)	(-3)	(-4)
     2	( 2 )	( 1 )	( 0 )	(-1)	(-2)	(-3)
     3	( 3 )	( 2 )	( 1 )	( 0 )	(-1)	(-2)
     4	( 4 )	( 3 )	( 2 )	( 1 )	( 0 )	( -1 )
     5	( 5 )	( 4 )	( 3 )	( 2 )	( 1 )	( 0 )

   • 2️⃣번 대각선의 경우, 열이 증가하면 행이 감소하는 y = -x + a 그래프이다.
     따라서 row+col값이 동일하다.

     	0	1	2	3	4	5
     0	( 0 )	( 1 )	( 2 )	( 3 )	( 4 )	( 5 )
     1	( 1 )	( 2 )	( 3 )	( 4 )	( 5 )	( 6 )
     2	( 2 )	( 3 )	( 4 )	( 5 )	( 6 )	( 7 )
     3	( 3 )	( 4 )	( 5 )	( 6 )	( 7 )	( 8 )
     4	( 4 )	( 5 )	( 6 )	( 7 )	( 8 )	( 9 )
     5	( 5 )	( 6 )	( 7 )	( 8 )	( 9 )	(10)

   • 다시말해, 1️⃣번 대각선은 row-col 값으로,
     2️⃣번 대각선은 row+col 값으로 특정할 수 있다.
     단, row-col은 음수가 나올 수 있기 때문에
     index로 사용할 경우 row-col+N을 이용하고,
     이때 두 대각선에서 나올 수 있는 index의 최대값은 (n-1)+n이므로
     배열의 길이는 2 * n으로 선언한다.

visited_diagonal_1 = [0 for _ in range(2*n)]
visited_diagonal_2 = [0 for _ in range(2*n)]
# (row, col)에 퀸이 위치할 경우 아래와 같이 방문 체크를 해준다.
# visited_diagonal_1[row-col+n] = 1
# visited_diagonal_2[row+col] = 1

이로서, 퀸을 위치시킴과 동시에
행, 열, 좌-우 대각선 모두 반복문 없이 방문체크를 할 수 있게 되었다.

[ 전체 코드 ]

import sys

n = int(sys.stdin.readline().rstrip())
visited_col = [0 for _ in range(n)]
visited_diagonal_1 = [0 for _ in range(n*2)]
visited_diagonal_2 = [0 for _ in range(n*2)]

count = 0

def solution(row):
    global count
    if row == n:
        count += 1
        return
    for col in range(n):
        if visited_col[col] == 0 and visited_diagonal_1[row+col] == 0 and visited_diagonal_2[row-col+n] == 0:
            visited_col[col] = 1
            visited_diagonal_1[row+col] = 1
            visited_diagonal_2[row-col+n] = 1

            solution(row+1)

            visited_col[col] = 0
            visited_diagonal_1[row+col] = 0
            visited_diagonal_2[row-col+n] = 0


solution(0)
sys.stdout.write(count)

결과 : Python3 시간 초과..?

📍탐색 시간 더 줄이기

여기서 탐색 시간을 어떻게 더 줄일 수 있을까?

🤲 반으로 나누자

첫번째 행의 열을 절반만 탐색한다.

1. if n % 2 == 0:
   열의 개수가 2로 나누어 떨어지므로
   첫 행의 한 쪽 절반을 탐색하며 계산된 경우의 수는
   첫 행의 다른 한 쪽 절반을 탐색하며 계산되는 경우의 수와 같다.

   따라서, 전체 경우의 수는 첫 행의 한 쪽 절반을 탐색하며 계산된 경우의 수 * 2 가 된다.

2. if n % 2 == 1:
   열의 개수가 2로 나누어 떨어지지 않으면,
   if n % 2 == 0: 일 때와 동일하게 계산할 경우
   첫 행의 가운데 열을 선택할 경우의 수가 계산되지 않는다.
   따라서,
   첫 행의 한 쪽 절반을 탐색하며 계산된 경우의 수 * 2 를 구한 뒤
   다시 첫 행의 가운데 열을 선택한 후 탐색하며 계산된 경우의 수 를 구해 더해준다.

[ 전체 코드 ]

import sys

N = int(sys.stdin.readline().rstrip())
visited_col = [0 for _ in range(N)]
visited_diagonal_1 = [0 for _ in range(N*2)]
visited_diagonal_2 = [0 for _ in range(N*2)]

count = 0

def solution(row, flag):
    global count
    if row == N:
        count += 1
        return
    for col in range(N//2, N//2+1) if (flag is True and row==0) else range(N//2) if row==0 else range(N):
        if visited_col[col] == 0 and visited_diagonal_1[row+col] == 0 and visited_diagonal_2[row-col+N] == 0:
            visited_col[col] = 1
            visited_diagonal_1[row+col] = 1
            visited_diagonal_2[row-col+N] = 1

            solution(row+1, flag)

            visited_col[col] = 0
            visited_diagonal_1[row+col] = 0
            visited_diagonal_2[row-col+N] = 0


solution(0, False)
count *= 2
if N % 2 == 1:
    solution(0, True)

sys.stdout.write(f'{count}')

결과 : Python3 성공 [ 30840kb / 20260ms ]