[코딩테스트 공부] N-Queen

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

풀이 전에 먼저 문제부터 분석해봐야죠?

주어진 문제를 읽어보면, N-Queen 문제는 브루트 포스 유형에 해당함을 금방 눈치를 챌 수 있습니다.

그러나, 시간 제한은 10초이므로 10억 회의 연산이 용납되고, N은 14까지 허용이 되기 때문에, 완전한 탐색을 수행하면 14^14 번의 연산을 수행하게 됩니다. 그렇게 되면, 10초는 아득히 넘게 걸리게 되므로, 탐색도 현명하게 해줘야합니다.

그래서, 저는 아래와 같은 생각을 가졌습니다!

어떤 생각을 가지고 풀이를 했을까요?

일단, 퀸은 위 아래, 대각선을 움직일 수 있기 때문에, 저희는 이런 생각을 가져야합니다 :

• 퀸을 놓되, 열이 겹쳐서는 안된다
• 대각선도 검사를 해줘야한다

첫번째 조건에 의하면, 저희는 퀸의 위치들이 0부터 N-1까지의 조합 형태로 등장해야함을 눈치챌 수 있습니다.

그리고, 이제는 대각선 검사가 문제인데, 검사를 수행할 때 마다 K번째 행에서 들어와서는 안되는 위치를 파악해서 그 위치를 제거해주면 됩니다.

코드를 분석하겠습니다.

코드부터 볼까요?

import sys

input = sys.stdin.readline

N = int(input())
visit_list = [False] * N
queen_info = {}
count = 0

def solution(k):
    global count
    
    if k == N:
        count += 1
        return
    
    for cand in range(N):
        if visit_list[cand] == False:
            if check_possible(k, cand):
                visit_list[cand] = True
                queen_info[k] = cand
                solution(k + 1)
                visit_list[cand] = False
            
def check_possible(k, cand):
    for key in range(k):
        value = queen_info[key]
        diff = k - key
        
        if value - diff == cand or value + diff == cand:
            return False
    return True
    
solution(0)
print(count)

코드를 음미해봅시다

재귀함수는 이제 알다시피, 탈출조건과 점화 관계가 매우 중요합니다!

탈출 조건은, k와 N이 일치하면 탈출하면 될것이고, 동시에 count를 1 늘려주면 될것입니다! (k == N이면 퀸이 모두 놓였다는 뜻)

문제는 점화 관계인데요...위에서 말했다시피, 퀸의 위치는 0부터 N-1까지의 조합 으로 뜨기 때문에, visit_list를 두어서 이전에 탐색했던 퀸의 열은 탐색하지 못하도록 막아버리면 됩니다.

그리고 이제 대각선 비교를 수행해야하는데요, 이를 위해서 check_possible이라는 메소드를 따로 두었습니다.

def check_possible(k, cand):
    for key in range(k):
        value = queen_info[key]
        diff = k - key
        
        if value - diff == cand or value + diff == cand:
            return False
    return True

queen_info에는 key로 퀸이 위치한 행, value로는 퀸이 위치한 열을 저장하였습니다.

이 때, 우리는 대각선 비교를 K번째 행으로 들어오면 안되는 위치 만 계산해주면 되기 때문에, 다음과 같이 비교를 하였습니다 :

if value - diff == cand or value + diff == cand:
     return False

value - diff, value + diff 모두 퀸의 위치 기준, K 행에서 걸리는 대각선의 위치입니다. 만일 cand가 이 위치에 걸리게 된다면, 그거는 다른 퀸에게 잡힐 수 있는 위치이므로, False를 반환하여 재귀함수 진행을 막아줍니다.

그리고 반복문 부분을 설명하겠습니다.

    for cand in range(N):
        if visit_list[cand] == False:
            if check_possible(k, cand):
                visit_list[cand] = True
                queen_info[k] = cand
                solution(k + 1)
                visit_list[cand] = False

queen_info[k] = cand를 통해서, K 행에 놓이는 퀸의 정보를 queen_info에 실어줍니다.

그리고, 재귀함수가 진행함에 따라서, queen_info[k]의 데이터는 계속 자동으로 갱신이 될 예정이기 때문에, del queen_info[k] 없이 반복문을 작성해도 괜찮습니다.