[BOJ][🟡4][백준#09663] N-Queen

문제 출처

BAEKJOON Online Judge #9663

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제

입력

8

출력

92

My Sol

def main(i):
    global N, V
    if i==N-1:
        for j in range(N):
            if j in V: continue
            if j-i in R: continue
            if j+i in L: continue
            return 1
        return 0

    cnt = 0
    for j in range(N):
        if j in V: continue
        if j-i in R: continue
        if j+i in L: continue

        V.add(j)
        R.add(j-i)
        L.add(j+i)

        cnt += main(i+1)

        V.remove(j)
        R.remove(j-i)
        L.remove(j+i)

    return cnt

N = int(input())
V, R, L = set(), set(), set()
print(main(0))

pypy로 풀어야 시간 초과가 나지 않는 방식이었다. 해시를 활용한 백트래킹과 브루트포스를 사용하였다.

1. 세로열, 오른쪽 위 대각선, 왼쪽 위 대각선을 각각 V, R, L의 set으로 두었다.
2. queen을 놓게 되면 해당 j, j+i, j-i의 값에 해당하는 위치를 또 둘 수 없다는 성질을 활용해 set에 넣어 in 연산자로 확인하였다.
3. dfs로 재귀적으로 경우의 수를 더했다.

결과

맞았습니다!!

모범답안

출처

#9663(N-Queen)
n=int(input())
count=0
row,left,right=[0 for _ in range(n)],[0 for _ in range(2*n-1)],[0 for _ in range(2*n-1)]#수직,왼쪽대각선,오른쪽 대각선
#인덱스의 합과 차가 같은 대각선상에 있을때 같다는 것을 이용함
#ex)0,2과 1,1과 2,0은 같은 대각선 상에 위치한다. 각행열의 합이 같은것을 알수있다.
 
def Q(i):
    global count
    if i==n:    #끝까지 퀸을 넣으면
        count+=1
        return
    for j in range(n):  #열을 이동하며
        if row[j] + left[i+j] + right[n-1+i-j]==0: #세조건에 걸리지 않는다면
            row[j]=left[i+j]=right[n-1+i-j]=1
            Q(i+1)
            row[j]= left[i+j]= right[n-1+i-j] = 0#초기화
 
Q(0)
print(count)

set이 아닌 list의 인덱스에 따른 0/1 체크로 조건을 확인하는 방식이다. 한 번에 0, 1로 조건 체크 및 초기화하는 방식인데 왜 연산속도가 더 빠른지는 알 수가 없다.