[백준] 9663번: N-Queen

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

9663번: N-Queen

백트래킹 문제이다. 어렵지 않아 보이지만 제한 시간을 맞추기가 너무나 힘들었다.

n = int(input())

grid = [[0]*n for _ in range(n)]

def attackable(r, c):
  for i in range(r):
    for j in range(n):
      if grid[i][j] == 1:
        if i == r or j == c or (r+c) == (i+j) or (r-c) == (i-j):
          return True

  return False

count = 0

def dfs(r, c):
  global count
  if attackable(r, c):
    return 

  if r == n-1:
    count += 1
    return

  grid[r][c] = 1

  for i in range(n):
    dfs(r+1, i)
    grid[r+1][i] = 0

for i in range(n):
  dfs(0, i)
  grid[0][i] = 0

print(count)

가장 처음 나이브하게 풀이한 알고리즘. NxN 크기의 배열을 만들어 퀸의 위치를 모두 체크해 주었다. 결과는 당연히 시간초과로 실패다. N의 최대 값인 15를 넣고 pc에서 돌려보면 10초는 커녕 무려 5분이 지나도 연산이 끝나지 않는다.

 

연산 시간을 줄이기 위해 중요한 것은 다른 공격 가능한 퀸의 위치를 찾는 attackable() 함수의 시간복잡도를 줄이는 것. 체스 판의 모든 좌표를 기록하기 보다는 앞선 퀸들이 현재 위치한 좌표만을 저장하는 배열 visited를 두기로 했다.

import sys

n = int(sys.stdin.readline().rstrip())

visited = []
count = 0

def attackable(r, c):
  for i, j in visited:
    if i == r or j == c or (r+c) == (i+j) or (r-c) == (i-j):
      return True
  return False

def dfs(r, c):
  global count
  if r == n-1:
    count += 1
    return 

  visited.append([r, c])

  for i in range(n):
    if attackable(r+1, i):
      continue

    dfs(r+1, i)

  visited.pop()

for i in range(n):
  dfs(0, i)

print(count)

그러나 이번에도 시간 초과로 실패. 일부 짜잘한 코드들을 수정해가며 계속해서 제출해봤지만 어림도 없다. 내가 생각하기에 위 코드는 파이썬이기 때문에 실패한 것 같다. (파이썬이라 당했다...)

 

내 머리로는 더 이상 최적화할 방법이 떠오르지 않아 좌절하고 있던 중 좌우 대칭인 점을 이용해 절반만 구하고 결과에 2를 곱하면 되지 않을까 생각이 들었다.

  // ...
  visited.pop()

# 결과를 절반만 구하고 2배 해준다.
for i in range(n//2):
  dfs(0, i)

count *= 2

# 만약 N이 홀수이면 가운데 값을 추가로 더해준다.
if(n%2):
  dfs(0, n//2)

print(count)

결과는 드디어 성공...! 3초나 걸렸지만 어쨌든 통과 했다. 언어는 꼭 pypy3를 선택해야 한다. 같은 코드를 python3로 제출하면 이 마저도 실패한다.

시간 제한을 맞추기 위한 수많은 발악들..