N-Queen (python)

프로그래머스 문제 N-Queen - LV3

https://programmers.co.kr/learn/courses/30/lessons/12952
백트래킹의 전형적인 문제

👀 깃헙 소스

문제설명
가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.
n은 12이하의 자연수 입니다.

입출력 예

n	result
4	2

솔루션
한 행에는 한 개의 queen 밖에 위치할 수 없다는 것을 이용하여
모든 행에 퀸이 위치하는 것이 가능할 때 answer을 1증가 시켜준다.
같은 열에 퀸이 위치해있거나 대각선에 위치한 퀸이 이미 있다면 다음열에 위치시켜본다. 가능한 경우 행을 증가시킨후 재귀함수를 호출하고 모두 불가능한경우 위치시킨 퀸을 제거하고 다음 열에 위치시킨다 (백 트래킹)

코드

# 파이썬
def dfs(n, y, col, diag1, diag2):
    global answer
    if y == n:
        answer += 1
        return

    for x in range(n):
        if x in col or (x + y) in diag1 or (x - y) in diag2:
            continue
        col.add(x)
        diag1.add(x + y)
        diag2.add(x - y)
        dfs(n, y+1, col, diag1, diag2)
        col.remove(x)
        diag1.remove(x + y)
        diag2.remove(x - y)


def solution(n):
    global answer
    col, diag1, diag2 = set(), set(), set()
    answer = 0
    dfs(n, 0, col, diag1, diag2)
    return answer

주의
answer은 primative한 변수이므로 global로 선언하여 값을 변경시켜주어야 한다.

참고
https://www.youtube.com/watch?v=0DeznFqrgAI