(Python) 백준 9663번 N-Queen - class 4

in Algorithm on BOJ

[문제 링크]

9663번 N-Queen

백트래킹 문제인데 대각선과 위아래가 겹치지 않는지 한 번에 처리하는 것이 중요하다. 따라서 정사각 보드판의 특성을 알고 있어야 한다.

  • 오른쪽 방향 대각선 : x - y 결과값이 같다면 같은 오른쪽 대각선 상
  • 왼쪽 대각선 : x + y 결과값이 같다면 같은 왼쪽 대각선 상
  • 같은 행 : 같은 x값
  • 같은 열 : 같은 y값

문제 조건에서 N * N 보드판에 N개의 퀸을 놓는다고 했다. 퀸은 같은 행에 존재할 수 없기 때문에 모든 행에 1개씩 퀸을 놓아야 한다. 따라서 행을 인자로 넘기면서 설계하면 된다.

cf) 백트래킹 문제는 타 언어보다 느리다는 파이썬의 특성상 PyPy3를 사용 해야 한다. 그리고 여기서는 재귀의 깊이를 늘리면 메모리 초과가 발생한다.

def queen(i):
    global ans
    if i == n: # 마지막 행까지 도달
        ans += 1
        return

    for j in range(n):
        # 새로 설치가 가능한 경우
        if column[j] == 0 and right[i - j] == 0 and left[i + j] == 0:
            # 설치 작업
            column[j] = 1
            right[i - j] = 1
            left[i + j] = 1

            queen(i + 1) # 다음 행

            # 설치 해제
            column[j] = 0
            right[i - j] = 0
            left[i + j] = 0


n = int(input())
ans = 0

column = [0] * n
right = [0] * (n * 2 - 1)
left = [0] * (n * 2 - 1)

queen(0)
print(ans)

© 2021. By Backtony