백준 9663번: N-Queen python

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

---

문제 요약

N x N 체스판 위에 퀸 N개를 놓을건데 서로 공격할 수 없게 놓는 경우의 수.

♛ 퀸(Queen)은 어떻게 움직일까?
퀸은 다음 방향으로 움직일 수 있다:
가로줄 전체 (→ ←)
세로줄 전체 (↑ ↓)
대각선 전체 (↘ ↖ ↙ ↗)

즉 퀸을 둘러싸고 있는 곳에는 퀸을 놓을 수 없다.

예를 들어 우선 N이 3이라면 3*3 체스판에 퀸 3개를 놓아야 하니
1. 1-1 에 놓는 경우

OXC
XXC
CCC

O : 퀸 , X: 퀸을 놓을 수 없는 곳, C : 퀸을 놓을 수 있는 곳
이렇게 인접한 곳이 자동으로 X로 정해지고, C중에 또놓고, 놓으면 또 놓을 수 있는 곳이 정해진다.
음 백트래킹 문제가 맞군.

그러면 체스판을 어떻게 정의할까?

2차원 배열을 생각할 수 있겠지만 2차원으로 저장시 조건 판별이 어려워보인다.

이 문제는 N에 따라 체스판 크기도, 퀸의 개수도 정해져서 1차원 배열로도 저장이 가능하다. (이게 핵심인듯)

만약 N = 4 인 경우,
queen = [1,3,2,4] 라고 하면 
index와 값을 묶으면 (0,1),(1,3),(2,2),(3,4) 가 된다.
이는 퀸의 위치가
OXXX
XXOX
XOXX
XXXO
됨을 의미한다.
이렇게 표현하면 
OXXX
OXXX
OXXX
OXXX 
(0,1),(0,2),(0,3),(0,4)
이렇게 같은 column 에 있을때는 표현할 수 없지만 
Queen의 공격 사정거리는 무한이라는 특징때문에 이는 카운팅에 포함될 수 없다.

그렇다면 backtrack 함수는 이런 형식이 되겠다

def backtrack():
	조건 1. 같은 row에 하나라도 있을 시 거름
    
    조건 2. 대각선에 위치하면 거름

대각선 위치에 있는 건 어떻게 알까?

이건 외우자
행 차이와 열 차이가 같으면 대각선에 있음
(1,2) (2,3) => 차이 1, 대각선

해답 및 풀이

import sys

N = int(sys.stdin.readline())
col = [0] * N  # col[row] = column_index (row행에 column_index열에 퀸을 둠)
count = 0     # 정답 (가능한 경우의 수)

def is_safe(row):
   for prev in range(row):
       if col[row] == col[prev] or abs(col[row] - col[prev]) == abs(row - prev):
           return False
   return True

def backtrack(row):
   global count
   if row == N:
       count += 1
       return

   for c in range(N):
       col[row] = c
       if is_safe(row):
           backtrack(row + 1)

backtrack(0)
print(count)

인데 python으로 제출시 시간초과가 나지만 pypy3으로 제출하면 해결된다.
python 해결법은 일단 보류하겠다..!