[백준-9663] N-Queen - Python

 

문제 소개

백트래킹 알고리즘을 공부하다 보면 항상 예시로 나오는 N-Queen 문제이다.
기본적으로 DFS로 다음 Node 탐색을 한다. 그러나 무조건 다음 Node로 넘어가는 것이 아니라
다음 Node 가 유의미할때만 Node를 탐색한다.
유의미 하지 않다면 그 Node는 끝을 낸다.

사용한 알고리즘

 

 

DFS ,백트래킹

 

Code

 

# Python code




import sys
import copy

sys.stdin = open("input.txt", "r")

###########################################################
import sys
import collections
import itertools
import copy

input=sys.stdin.readline
n = int(input())

ans = 0
Columns = []
Candidate = list(range(n))


def Check(Columns_,candi):
    len_ = len(Columns_)
    if len_ == 0:
        return True
    for col_ , value_ in enumerate(Columns_):
        if (len_ - col_) == abs(value_ - candi):
            return False
    return True



def DFS(Columns_ , Candidate_):
    global ans
    # End Condition
    if len(Columns_)==n:
        ans += 1
        return
    #print("Search")

    # Search
    for i_ in range(len(Candidate_)):
        candi = Candidate_[i_]
        next_Candi = Candidate_[:i_]+Candidate_[i_+1:]
        next_Columns_ = Columns_+[candi]

        #print("For"+" ",candi)
        if Check(Columns_,candi):
            #print("Check T" , next_Columns_ , next_Candi )
            DFS( next_Columns_ , next_Candi )



DFS(Columns,Candidate)

print(ans)

※ end