https://www.acmicpc.net/problem/9663
9663번: N-QueenN-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.www.acmicpc.net
벽느낀다. ㅋㅋㅋㅋ
처음에는 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 Truedef 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)