[Programmers] N-Queen

1. 문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

입출력 예

n	result
4	2

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

2. 해설

N-Queen 문제는 백트래킹 설명할 때 단골로 나오는 예제다. 잠시 체스 룰을 설명하자면 퀸은 상, 하, 좌, 우, 대각선 방향으로 원하는 칸 수 만큼 이동할 수 있다. 그래서 첫번째 줄부터 하나씩 놓고, 두 번째 줄에 하나씩 놓아보면서 안되면 다시 뒤로 가는 식의 백트래킹을 브루트 포스처럼 해주면 답이 나온다.

여기서 시간 복잡도를 줄이기 위해 1차원 배열을 사용한다. 예를 들어 col[x] = y라면 col[x][y]에 퀸이 놓여 있다는 뜻으로 해석하자. 탐색하는데 1차원 배열이 2차원 배열보다 더 빠르니까.

3. 코드

board = 0 #체스판의 크기
res = 0
col = [0] * 12 # 체스판은 최대 12*12까지

def check(lv):
    global col
    
    for i in range(lv):
    	#상하좌우나 대각선 방향에 퀸이 놓여 있을 경우
        if col[i] == col[lv] or abs(col[lv]-col[i]) == lv - i: 
            return False
    
    return True

def nqueen(x):
    global board, res, col
    if x == board: #n번째 칸까지 다 놓았다면 결과값 증가
        res+=1
    else:
        for i in range(board):
            col[x] = i
            if check(x): #놓을 수 있는 위치라면 다음 줄로 넘어감
                nqueen(x+1)
        

def solution(n):
    global board, res
    board = n
    
    nqueen(0)
    
    return res

4. 여담

백준 N-Queen

백준에 이 문제랑 똑같은 게 있다. 그런데 백준은 n의 크기가 최대 15까지이고, 시간 제한이 좀 더 깐깐한지 위의 코드를 숫자 바꿔서 제출하니까 시간 초과가 뜬다. 그래서 파이썬으로 풀려면 다른 방법을 찾아야 할 듯 하다. 나는 그냥 C++로 제출했다. 이렇게 보니 고수들이 C++을 쓰는 데는 다 이유가 있다는 걸 느꼈다.