[프로그래머스 Lv2] N-Queen (Python)

 

---

 

def Promising(pan, y, depth) :    
    for i in range(depth) :
        if y == pan[i] or (depth-i == abs(y-pan[i])): 
            return False
    return True

def Nqueen(n, pan, depth) :
    global answer  
    
    if depth == n :
        answer += 1
    else :
        for y in range(n) : 
            if Promising(pan, y, depth) :
                pan[depth] = y
                Nqueen(n, pan, depth+1)
            
def solution(n):
    global answer
    answer = 0
    
    pan = [0] * n
    Nqueen(n, pan, 0)
    
    return answer

 

백트래킹 문제 첨 풀어보는거라 엄청 헷갈리고 .. 엄청 헤매고 ..

유튜브에서 N-Queen 강의도 봤는데 막상 강의 닫으니까 또 헤매고..웅웅,,,

 

 

나중가면 또 기억 못 할 것 같으니께 ,,

최대한 자세하게 설명 써놓겠다 ..!!

 

 

 

 

def solution(n):
    global answer
    answer = 0
    
    pan = [0] * n
    Nqueen(n, pan, 0)
    
    return answer

 

n x n 표니까 2차원 배열로 만들어야 되지 않나? 라고 생각했는데

어차피 한 줄에 하나만 들어갈 수 있으니까 걍 1차원 배열에 열 번호를 넣으면 되겠다 !! 해서

예를 들어 4x4 판이면 pan = [0, 0, 0, 0]  형태로 초기화시켜줬다

 

그리고 Nqueen() 함수 파라미터에는 아래 3가지를 줌.

 

n : 가로/세로 길이

pan : 퀸의 열 번호가 담긴 1차원 배열

depth : 깊이 (0부터 시작)

 

 

 

 

def Nqueen(n, pan, depth) :
    global answer  
    
    if depth == n :
        answer += 1
    else :
        for y in range(n) : 
            if Promising(pan, y, depth) :
                pan[depth] = y
                Nqueen(n, pan, depth+1)

 

이게 이제 진전시키는 ..? 이라고 해야 되나

유망 조건에 맞으면 계속 재귀 함수로 부를 Nqueen 함수

 

depth 는 0부터 시작하니까 결국 끝까지 가서 n 과 같게 되면

조건을 모두 충족하는 거니까 answer += 1 해주고,

 

만약 그게 아니라면 열 하나씩 순회하면서

Promising() 함수 호출해서 유망한지 아닌지 확인함 !!

 

유망 함수에서 반환하는 값이 True 면 

해당 열 번호 (y) 를 pan 배열에 집어넣고,

depth  하나 올려서 Nqueen() 재귀호출하면 됨.

 

 

 

 

def Promising(pan, y, depth) :    
    for i in range(depth) :
        if y == pan[i] or (depth-i == abs(y-pan[i])): 
            return False
    return True

 

이건 이제 해당 depth 에서 앞으로 진행할 열 번호 (y) 가

조건에 맞는지 확인하는 함수

 

1) 같은 열에 퀸 중복 x

2) 대각선에 퀸 중복 x

 

depth 이전 행까지 for 문 돌면서 위 2가지 조건을 검사함

하나라도 해당되면 바로 False 반환하도록 !! 그럼 끝 ㅎㅅ