Baek_63512

어제 까페에서 공부해본 문제이다. N-Queen은 백트랙킹 문제중에 가장 유명한 문제이고 솔직히 백트랙킹에 취약해서 이 문제를 도전해봐야겠다는 생각은 했는데.... 결국 금방 답을 찾아보게 되었다.

내가 본 백트랙킹의 포인트는 dfs 구조에서 조건을 함수의 구조로 만든 것이다..
실제로 dfs를 만들시 나는 조건으로 방문조건을 넣었는데 그런 느낌으로 조건을 함수 형태로 만들고 dfs를 시키는 것이다.

import sys
input = sys.stdin.readline

N = int(input())
ans = 0
row = [0]*N


def checking(x):
    for i in range(x):
        if row[x] == row[i] or abs(row[x]-row[i]) == abs(x-i):
            return False
    return True


def n_queen(x):
    global ans
    if x == N:
        ans += 1
        return
    else:
        for i in range(N):
            row[x] = i
            if checking(x):
                n_queen(x+1)


n_queen(0)
print(ans)

checking이 조건인데 실제 이 문제는 이중배열에서 체스를 놓는 문제이다. 하지만 column의 위치를 index이고 row의 위치를 list 안에 넣어서 표현하면 되기 때문에 단일 배열로 풀이가 가능하다.

checking 안에 조건이 결국 N-Queen을 푸는데 가장 중요한 열쇠인데 대각선을 특히 확인해주는 포인트가 가장 중요하다.
or로 이루어진 앞뒤 두 조건은 먼저 앞쪽은 값이 같다는 것은 같은 row 상에 위치한다는 개념이니 탈락이다. 뒤에는 대각선 상에 존재하는지 확인해준다.

이렇게 True나 False를 뱉을 수 있는 함수 구성 후 dfs 탐색 방식대로 재귀 탐색을 사용하면 된다.

rox[x] = i

이 부분이 체스를 놓는 부분이다.

솔직히 처음부터 내가 구상하기란 정말 어려운 문제이다... 그래도 백트랙킹 문제는 정말 중요하고 특히 삼성에서 시뮬레이션과 더불어 많이 내는 방식인것 같다. 열심히 익혀야겠다.