[백준][9663번][DPS] N-Queen

N-Queen

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

<문제>

<코드>

def promising(i):
    for j in range(0,i):
        # 새로운 퀸과 기존의 퀸이 같은 행에 있거나 대각선에 있을 경우
        if row[j] == row[i] or abs(row[j]-row[i]) == (i-j):
            return False
    return True
 
def N_queen(i):
    global result
    if i == N:
        result += 1
    else:
        for j in range(N):
            row[i] = j
            if promising(i):
                N_queen(i+1)
 
 
N = int(input())
row = [0]*15
result = 0
N_queen(0)
print(result)
 

<문제 푼 요령>

1. NxN 체스판에 N개의 퀸을 놓는 경우의 수를 구하는 것이 문제이므로 한 열당 퀸을 1개씩 놓을 수 있다. 그러므로 퀸을 1열부터 N열까지 놓는다고 생각하면 i열에 있는 퀸의 행의 값을 row[i]로 표현할 수 있다.

2. 이 문제는 브루트포스 문제인데 브루트 포스 문제는 모든 경우의 수를 다 돌려보는 것을 말한다. 그러나 특정 조건의 경우의 수만 돌려보도록 하기 위해서 한정 함수라는 것을 두게 되는데 이 문제에서는 promising이라는 함수를 사용하였다. 

3. N_queen이라는 함수에서 dfs 알고리즘을 수행하는데 처음 if 문은 무한루프를 탈출하기 위한 기능이고, 한정 함수의 조건을 만족하면 재귀함수로 들어가게 된다. 재귀함수는 다음 열로 계속 진행시켜 주는 것이고 for j in range(N) 부분은 행을 다음 행으로 계속 진행시켜 주는 것이다.