방구석프로의 이야기

https://www.acmicpc.net/problem/9663

문제 해결을 위한 과정

이 문제의 경우 백트래킹을 통해 해결할 수 있는 문제였습니다. Queen의 경우 같은 열 혹은 같은 행에 있거나 같은 대각선에 있는 곳을 이동할 수 있습니다. 따라서 다음 그림과 같이 퀸을 놓을 수 있습니다. (단, n이 4 인 경우)

같은 행에는 다시 queen을 위치할 수 없고, 시간복잡도를 위해 2차원 배열을 1차원 배열로 단순화해서 표시할 수 있습니다. 위 그림의 경우는 다음과 같습니다. arr = [1, 3, 0, 2] 해석하면 0번째 인덱스(행)의 1번째 인덱스(열), 1번째 인덱스(행)의 3번째 인덱스(열), 2번째 인덱스(행)의 0번째 인덱스(열), 3번째 인덱스(행)의 2번째 인덱스(열)에 위치했다는 뜻입니다. 이를 완전탐색 식으로 표현하면 아래의 코드와 같습니다. 중요한 검사 로직은 같은 열에 있는지(check함수의 첫 번째 if문), 대각선에 있는지(check 함수의 두 번째 if문)으로 검사합니다. 이때 같은 행인 경우는 존재할 수 없는데 배열의 인덱스 자체가 행을 의미하기 때문에 같은 행에는 queen이 무조건 없습니다.

소스코드

n = int(input())
arr = [0] * n
count = 0

def dfs(depth):
  global count
  if depth == n:
    count += 1
    return

  for i in range(n):
    arr[depth] = i
    if check(depth):
      dfs(depth + 1)

def check(col):
  for i in range(col):
    if arr[i] == arr[col]:
      return False
    elif abs(i-col) == abs(arr[i]-arr[col]):
      return False
  return True

dfs(0)
print(count)