백준 9663 n-queen

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

9663번: N-Queen

벽느낀다. ㅋㅋㅋㅋ

처음에는 2차원배열을 통해 풀었는데, 시간초과가 났다.

다른사람의 풀이를 보고 힌트를 얻었다.

dp[i]=j 의 뜻은, i번째 줄의 j번째 칸에 퀸을 놓는다는 소리이다.

 

모든 열에는 퀸이 하나씩 들어가야 하므로, 0열부터  n가지의 경우를 모두 탐색한다.

이후 그 다음 열을 순차적으로 탐색하며, 안되는 경우 

(가로는 짜피 순차적으로하기때문에 겹치지 않으므로, 세로와 대각선만 생각)

즉 이전 dp[i-1]의 값이 지금dp[i] 와 같거나, 대각선을 방지하기 위해  같은 기울기가 아니면

(지금열-이전열)== |지금행-이전행| 이 True라는건 기울기가 같다는 뜻!!

거기서부터의 경우를 베제한다.

 

만일 깊이가 7인 곳에 도달했으면, answer에 1을 더해준다.

def check(depth):
    for i in range(depth):
        if dp[depth]==dp[i] or (depth-i==abs(dp[depth]-dp[i])):
            return False

    return True

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

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


answer=0
n=int(input())

# 어떻게 되든 한 줄에 2개이상 들어갈 수 없음
dp=[0 for _ in range(n)] #dp[i]=j  i번째 줄에 j를 놓는다.
dfs(0)
print(answer)