[Python, 파이썬] SWEA 2806. N-Queen

 

퀸은 같은 행, 열, 대각선에 있는 애를 공격한다.

NxN 체스보드에 N개의 퀸을 서로 공격하지 못하게 놓는 문제.

 

 

def BFS(now, num): # 현재 행, 남은 퀸의 개수

    global ok # n-queen 경우의 수
    global memo # 퀸 저장 위치 
    
    if(num <= 0): # 퀸이 모두 사용된 경우
        ok += 1 # 경우의 수 +1
        return

    for j in range(N):
        if(j not in memo) and safe(now, j): # 대각선, 행 확인
            
            memo[now] = j # 퀸 저장
            
            BFS(now+1, num-1) # 다음번 퀸 위치 탐색

            memo[now] = -1 # 백트래킹
        

def safe(row, value): # 대각선 확인
    for i in range(row):
        if (abs(memo[i]-value) == abs(i-row)): # 대각선에 존재 시
            return False
    return True
    
T = int(input()) # 테스트 케이스의 개수

for test_case in range(1, T+1):

    N = int(input()) # 자연수 N
    memo = [-1]*(N) # 퀸 위치 저장
    ok = 0 # n-queen 경우의 수
    
    BFS(0, N) # 백트래킹 탐색

    print('#%d %d' %(test_case, ok))

 

 

 

[문제풀이]

---

BFS+백트래킹을 사용해서 N-Queens 문제를 풀었다.

각 퀸은 같은 행, 같은 열, 그리고 대각선에 위치한 다른 퀸을 공격할 수 있다.

즉, 한개의 행과 한 개의 열에는 딱 1개의 퀸만 놓을 수 있단 뜻이다.

 

memo = [-1]*(N) # 퀸 위치 저장

 

그래서 일차원 배열에 놓은 퀸의 위치를 저장해서, (j not in memo)로 현재 위치가 이미 저장된 건지 확인했다.

이때 대각선은 바로 이전 행에 놓은 것만 확인하면 되는 게 아닌, 전체 퀸의 대각선 여부를 확인해야 하므로 따로 함수로 뺐다.

def safe(row, value): # 대각선 확인
    for i in range(row):
        if (abs(memo[i]-value) == abs(i-row)): # 대각선에 존재 시
            return False
    return True

 

대각선이란 두 퀸의 행 차이와 열 차이가 같다는 의미이므로, 저장한 퀸의 위치들과 현재 놓을 위치를 계산해 체크하였다.

 

memo[now] = j # 퀸 저장
BFS(now+1, num-1) # 다음번 퀸 위치 탐색
memo[now] = -1 # 백트래킹

 

 

그 후 대각선과 열을 체크해서 맞으면 퀸을 저장하고, 다음번 행의 퀸을 놓을 위치를 BFS를 다시 호출하고 백트래킹 한다.