[PG/Python] N-Queen

📌 문제

https://programmers.co.kr/learn/courses/30/lessons/12952

코딩테스트 연습 - N-Queen

 

📌 문제 접근 방법

1. 어차피 한 행에 하나의 퀸만 놓을 수 있으므로 행을 하나씩 늘려가며 재귀함수를 돌리고, 행이 n과 같아지면 n개의 퀸을 모두 놓았다는 뜻이므로 answer를 1 더해주고 리턴하는 방식으로 구현하였다.
2. cols, minus, plus라는 리스트를 만들었는데,
   cols는 각 열에 하나의 퀸만 놓을 수 있으므로 지금 놓여있는 퀸의 열을 저장하는 리스트이고
   minus, plus는 대각선으로 겹치지 않게 하기 위해 만든 리스트이다.
   (왼쪽에서 오른쪽으로 내려가는 대각선은 좌표의 행-열의 값이 모두 같고, 오른쪽에서 왼쪽으로 내려가는 대각선은 좌표의 행+열의 값이 모두 같다.)
3. 해당 열, 대각선으로 겹치지 않는다는 것을 확인하면 각각의 값을 리스트에 추가하고 다음 행으로 넘어가도록 row+1로 재귀를 돌리고, 해당 위치에 퀸을 놓지 않았을 경우도 확인하기 위해서 다시 값을 빼준다.
4. 위의 과정을 반복하여 answer를 반환해준다.
5. +) 추가로 나는 행-열, 행+열 의 값을 통해 대각선을 판단해줬는데, 이전 좌표와 현재 좌표의 기울기 값을 통해서 대각선을 판단하는 방법도 있다!

 

📌 코드

def solution(n):
    cols = []
    minus = []
    plus = []
    
    answer = 0
    def queen(row):
        nonlocal n, answer
        
        if row == n:
            answer += 1
            return
        
        for col in range(n):
            if col not in cols and row-col not in minus and row+col not in plus:
                cols.append(col)
                minus.append(row-col)
                plus.append(row+col)
                
                queen(row+1)
                
                cols.remove(col)
                minus.remove(row-col)
                plus.remove(row+col)
    
    queen(0)
    
    return answer