SWEA 2806. N- queen _ python

 

 

N-queen 문제

 

 

 

처음에 N-Queen 문제를 봤을 땐 어떻게 접근해야할 지 몰랐고, 이해가 가는 풀이가 없었다.

 

그런데 아래 풀이를 통해 이해에 도움을 받아 정리해둔다!!

 

첫번째는 가로, 세로(i, cols) + 대각선(diagonal) 을 검사했다.

 

대각선의 경우에는 이전에 입력된 좌표의 값과 입력할 좌표의 값의 차이가 똑같다는 것을 이용해 푸는 것이다.

 

 

 

두번째는

 

4 * 4 배열일 경우, row와 col을 더하면 아래와 같이 나타나진다.

 

이런 경우, 대각선끼리 숫자가 같게 되므로 동일한 숫자를 가진 좌표들이 동일 대각선에 위치함을 이용해 푸는 것이다!!

 

0 1 2 3

1 2 3 4

2 3 4 5

3 4 5 6

 

하지만, 위의 경우는 오른쪽 대각선만 알 수 있으므로 왼쪽 대각선도 따로 구해야 한다.

 

왼쪽 대각선을 구할 땐 row - col을 하면 아래 와 같이 왼쪽 대각선에 같은 숫자들이 위치한다.

 

편의를 위해 N 을 더해준 다음 계산하면 된다.

 

0 -1 -2 -3 

1  0 -1 -2

2  1  0 -1

3  2  1  0

 

 

 

 

 

 

#########첫번째 풀이
def diagonal(row, col):
    for i in range(row):
        if row - i == abs(col-picked[i]):
            return True
    return False

def N_queen(idx):
    global ans
    if idx == N:
        ans += 1
        return
    for i in range(N):
        if cols[i] or diagonal(idx, i): continue
        cols[i] = 1
        picked[idx] = i
        N_queen(idx+1)
        cols[i] = 0

for tc in range(1, int(input())+1):
    N = int(input())
    cols = [0] * N
    picked = [0 for _ in range(N)]
    ans = 0
    N_queen(0)
    print('#{} {}'.format(tc, ans))


############## 두번째 풀이



def nQueen(k):
    if k == N:
        global ans; ans += 1
    else:
        for i in range(N):
            a, b = k + i, k - i + N -1
            if col[i] or line1[a] or line2[b]: continue
            col[i] = line1[a] = line2[b] = 1
            nQueen(k + 1)
            col[i] = line1[a] = line2[b] = 0



for tc in range(1, int(input())+1):
    N = int(input())
    col = [0] * N
    line1 = [0] * (N * 2 - 1)
    line2 = [0] * (N * 2 - 1)
    ans = 0
    nQueen(0)
    print('#{} {}'.format(tc, ans))