[백준 2024/09/09] 9663번 N-Queen

1. 문제

https://www.acmicpc.net/problem/9663

 

2. 접근 방법

 

체스판에서, 대각선으로 겹치는 지 유무를 확인하기 위해, x y값들 더한 것과, x y 값을 뺀 것을 list로 만들어서 확인해 두려고 한다.

 

또한 y 축으로 겹치는 것을 확인하기 위해서의 리스트도 하나 만들어 두려고 한다.

minus라는 list를 만들면서, 음수의 값이 들어갈 수도 있지 않을까 라고 생각을 하였지만, y-x로 빼게 된다면 음수의 값은 들어가지 않는다.

- 처음에 음수값이 들어갈 것을 염려해, defaultdict 로 구현을 했었었다. 

 

탈출 조건은 y축이 조건을 만족하면서 4에 도달했을 때이다.

4에 도달하게 되면 count + 1을 해주고, return 을 해주어 마무리를 해준다.

 

queen을 놓을 수 있는 자리를 찾을 때마다 x+1을 해준 후, 재귀적으로 함수를 다시 부르면 된다.

 

3. 코드

count = 0


def n_queen(n, x, plus, minus, x_axis):
    global count
    if x == n:
        count += 1
        return

    for y in range(n):
        if plus[x + y] == 0 and minus[y - x] == 0 and x_axis[y] == 0:
            plus[x + y] = minus[y - x] = x_axis[y] = 1
            n_queen(n, x + 1, plus, minus, x_axis)
            plus[x + y] = minus[y - x] = x_axis[y] = 0


if __name__ == "__main__":
    n = int(input())
    plus = [0] * (2*n)
    minus = [0] * (2*n)
    x_axis = [0] * n
    n_queen(n, 0, plus, minus, x_axis)
    print(count)