백준 9663번 - Python

백준 9663번 - N-Queen

생각한 풀이

우선 퀸의 범위는 상 하 좌 우 대각선이다.
그렇다면 퀸은 한 열, 행에 하나씩만 들어갈 수 있고, 그렇게 되면 상 좌 우는 확인할 필요가 없어진다.
만약 현재 노드가 (0, 0)이면 (1, 1)이 대각선이다. 0 - 1 = 0 - 1이 된다. (1, 0) 이면 (2, 1)이 대각선이다. 1 - 2 = 0 - 1 이기 때문이다.
그러므로 대각선을 구하는 공식은 row - row = col - col이 된다.
한 row당 하나의 퀸이 들어갈 수 있기 때문에 인덱스를 깊이로 생각하면 1차원 배열로 구현이 가능해진다.
1. N을 입력받아 0으로 채워진 1차원 배열을 만든다.
2. dfs의 파라미터로 depth(깊이)를 주어준다.(시작 깊이 = 0)
3. 만약 depth가 N과 같다면 모든 깊이에 대한 찾기가 완료된 상태이다.
4. 같지 않다면, graph의 현재 깊이에 i번째 열에 퀸을 넣어 만약 그 행에 둔 퀸이 같은 열에 다른 퀸이 없으며 대각선상에도 다른 퀸이 없다면 True를 리턴하여 다음 행을 확인한다.(재귀)

코드

pypy3으로만 가능.

N = int(input())
graph = [0] * N
count = 0

def promissing(depth):
  for j in range(depth):
    if graph[depth] == graph[j] or abs(depth - j) == abs(graph[depth] - graph[j]):
      return False
  return True

def dfs(depth):
  global count
  if depth == N:
    count += 1
    return
  for i in range(N):
    graph[depth] = i
    if promissing(depth):
      dfs(depth + 1)
dfs(0)
print(count)

결과