[Baekjoon] 9663. N-Queen

# Problem

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 퀸은 대각선, 좌우상하 이동가능 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

# Solution 1

def check(x): # 상하좌우, 대각선 확인
    for i in range(x):
        if row[x]==row[i]:
            return False
        if abs(row[x]-row[i])==x-i:
            return False
    return True

def dfs(x):
    global result
    if x==n:
        result+=1
    else:
        for i in range(n):
            row[x]=i
            if check(x): # 해당 행에 놓아도 괜찮은 경우 다음행으로 넘어가기
                dfs(x+1)
                
n = int(input())
row = [0]*n
result=0
dfs(0)
print(result)

 

# Solution 2 -  시간 초과

def available(candidate,current_col):
    current_row = len(candidate)
    for queen_row in range(current_row):
        if candidate[queen_row] == current_col or abs(candidate[queen_row]-current_col)==current_row - queen_row:
            return False
    return True
def dfs(N, current_row, current_candidate, final_result):
    if current_row == N:
        final_result.append(current_candidate[:])
        return
    for candidate_col in range(N):
        if available(current_candidate, candidate_col):
            current_candidate.append(candidate_col)
            dfs(N,current_row+1,current_candidate,final_result)
            current_candidate.pop()
    
n = int(input())
final_result=[]
dfs(n,0,[],final_result)
print(len(final_result))