[백준] 9663번 N-Queen

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

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

---

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

---

예제 입력 1

8

예제 출력 1

92

---

풀이

N-Queen 문제는 백트래킹 알고리즘으로 풀 수 있는 대표적인 문제입니다. 백트래킹은 완전탐색(주로 DFS)+조건문(가지치기)으로 생각할 수 있으며, 자세한 설명은 다음을 참고하면 됩니다.

참고 풀이: https://velog.io/@rapsby/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-N-Queen-python

for문과 쓰이는 else문:
https://studymake.tistory.com/208

---

소스코드

import sys
input = sys.stdin.readline #입력빠르게받기
#sys.setrecursionlimit(10 ** 6) ##재귀를 사용하므로(★이 문제에서 재귀깊이 늘리면 메모리초과!!)

def dfs(queen, row, N):
  count = 0 #이때의 경우의 수 저장할 변수

  if N == row: #체스판 넘어감
    return 1
  
  for col in range(N): #0부터 N-1번째 열까지
    #if visited[col]:
    #  continue

    queen[row]=col #row번째 행의 col번째 열에 퀸 위치시키기

    for i in range(row): #0부터 row-1번재 행까지
      if queen[i] == queen[row]: #같은열에 존재할 경우
        break
      if abs(queen[i]-queen[row]) == row -i: #대각선안에 존재할 경우
        break

    else: #★for문과 짝을 이룬 else문(for문에서 break하면 얘도 수행X)
      #visited[col] = True
      count += dfs(queen, row+1, N) #row 한칸 이동해서 그때의 경우의수 더하기
      #visited[col] = False

  return count
      

N=int(input())
queen = [0]*N #queen[row] = col, row번째 행에는 col열에 queen 위치
#visited=[False]*N
print(dfs(queen, 0, N)) #0번째 행부터 경우 살피기

sys.setrecursionlimit을 적용했을 때, pypy3에서 메모리초과가 났었고, 주석처리하니 AC처리 받았습니다.
그리고 visited로 방문처리를 통해 위 코드를 더욱 최적화할 수 있습니다.