[SWEA/Python] 2806. N-Queen

📌 문제

https://swexpertacademy.com/main/main.do

SW Expert Academy

 

📌 문제 접근 방법

1. 행, 열, 대각선 이동을 전부 해야하나? 고민을 하다가 결국 구글링을 하고 set으로 만들어주면 된다는 것을 알게 되었다.
   set을 사용할 때는 add, remove를 통해 요소를 넣고 뺄 수 있다.
2. 처음엔 행도 set을 통해서 공격여부를 판단했었는데, 시간초과가 나서 행은 set을 없애주고 행 단위로 함수를 실행시켜주는 걸로 바꾸었다.

 

📌 코드

import sys
sys.stdin = open('input.txt')

def find_next(i):
    global answer

    if i == N:
        answer += 1
        return

    for j in range(N):
        if (j in col) or (i-j in l_to_r) or (i+j in r_to_l):
            continue

        col.add(j)
        l_to_r.add(i-j)
        r_to_l.add(i+j)

        find_next(i+1)

        col.remove(j)
        l_to_r.remove(i-j)
        r_to_l.remove(i+j)

            

T = int(input())

for t in range(1, T+1):
    N = int(input())

    answer = 0

    col = set()
    l_to_r = set()
    r_to_l = set()

    find_next(0)

    print('#{} {}'.format(t, answer))