[Python] SWEA 2806번 N-Queen

문제

SW Expert Academy

문제 풀이

• 퀸이 같은 열, 행 대각선 내에 없도록 탐색을 진행해야 한다 <- 백트래킹 사용
• 같은 대각선 내 (오른쪽)에 있을 때 행과 열의 인덱스를 더한 값이 같고, 왼쪽 대각선에 있을 때는 행과 열의 인덱스를 뺸 값이 같다.
  • 같은 열, 대각선 내에 있는지 빠르게 체크하기 위해 v1,v2,v3배열을 만들어, 접근하여 0이 저장되어 있다면, 같은 행이나 대각선에 퀸이 없는 것으로 퀸을 놓을 수 있는 경우로 보고, 1이 저장되어있다면, 퀸을 놓을 수 없는 경우로 본다.
• 같은 열, 대각선의 인덱스 값이 0이라면 위에서 말한대로 퀸을 놓을 수 있으므로, 값을 1로 바꾸고, 재귀적으로, 현재 행 인덱스에 1을 더한 값을 넣어 다음 행의 가능한 경우를 탐색한다.
• 위의 모든 과정을 반복한 후, 행이 N이라면 모든 행에 퀸이 겹치지 않게 놓은 경우이므로, 카운트 한 후, 종료한다.
• 이 과정을 반복하면 ans에 총 몇가지 경우의 수가 있는지 저장 되어있으므로, 형식에 맞게 출력한다. 

코드

def dfs(i):
    global ans
    # i는 행의 인덱스
    if i == N:
        ans += 1
        return

    for j in range(N):
        # 같은 열, 오른쪽 대각선, 왼쪽대각선에 퀸이 없다면
        # 퀸 놓고 아래 행 탐색
        if v1[j] == v2[i + j] == v3[i - j] == 0:
            v1[j] = v2[i + j] = v3[i - j] = 1
            dfs(i + 1)
            # 놓은 퀸들 초기화
            v1[j] = v2[i + j] = v3[i - j] = 0

t = int(input())
for tc in range(t):
    N = int(input())
    ans = 0
    v1 = [0] * N
    v2 = [0] * (2 * N) # 대각선 왼쪽 아래에 있는지 탐색
    v3 = [0] * (2 * N) # 대각선 오른쪽 아래에 있는지 탐색
    dfs(0)
    print(f'#{tc + 1}', ans)

참고 자료