[프로그래머스] N -Queen

접근

엉엉..ㅠ 어려운 문제였다.. 예전에도 못풀고 포기했었던 문제였는데 이번에는 리더님의 도움을 받아 간신히 풀 수 있었다

 

크게 search, check 파트로 나뉜다.

1. search 함수
   • dfs를 이용하여 모든 경우의 수를 순회한다
   • for loop이 0부터 n까지 돌아간다(이 부분을 잘하면 최적화를 할 수 있을 것같긴 하다)
   • 현재 x 자리에 순회하면서 업데이트 되는 값들을 넣어주고(y값들)
   • check했을 때 True라면 그 다음 자리인 x + 1 자리로 넘어가서 다시 탐색한다. (dfs 방식)
     • loop 한 턴에 한 column 씩 확인
2. check 함수
   • 현재 위치와 값이 주어진 조건에 부합하는지 확인하고, boolean을 리턴한다

 

개념이 살짝 말로 하기 어려워서 그림으로 잘 풀어내봤는데 미래의 내가 다시 보았을 때도 이해할 수 있기를..ㅎ

 

 

 

코드

from collections import deque

def solution(n):
    return search(n, 0, deque([0] * n))

def search(n, x, stack):
    answer = 0
    if n == x:
        return 1
    
    for y in range(n):
        stack[x] = y
        if check(x, stack):
            answer += search(n, x + 1, stack)
            
    return answer

def check(x, stack):
    for y in range(x):
        if stack[y] == stack[x] or abs(stack[y] - stack[x]) == x - y:
            return False
    return True