https://www.acmicpc.net/problem/9663
나에게는 숙적 같은 문제였는데 해결하게 돼서 기쁘다
C언어로 풀 때는 이차원배열을 복사해서 풀었는데
한줄에 퀸이 하나씩만 올 수 있다는 것을 이용해 N칸의 일차원 배열에 각 row의 퀸의 위치 col을 저장하여 풀었다.
def dfs(cur, cnt):
for n in range(N):
arr[cur] = n
attacked = False
for i in range(cur):
if arr[i] == n:
attacked = True
break
if (cur - i) == abs(n - arr[i]):
attacked = True
break
if not attacked:
if cur < (N - 1):
cnt = dfs(cur + 1, cnt)
else:
return cnt + 1
return cnt
N = int(input())
arr = [0]*N
print(dfs(0, 0))
또는
def dfs(cur, cnt):
for n in range(N):
arr[cur] = n
attacked = False
for i in range(cur):
if arr[i] == n:
attacked = True
break
if (cur - i) == abs(n - arr[i]):
attacked = True
break
if not attacked:
if cur < (N - 1):
cnt = dfs(cur + 1, cnt)
else:
return cnt + 1
return cnt
N = int(input())
arr = [0]*N
print(dfs(0, 0))
다른 사람의 코드
rkaxhdals
https://www.acmicpc.net/source/34382631
def rec(y, n):
ans = 0
for x in list(s):
for i in range(1, y + 1):
if abs(x - arr[y - i]) == i: break
else:
if y == n - 1: ans += 1
else:
arr[y] = x
s.remove(x)
ans += rec(y + 1, n)
arr[y] = -1
s.add(x)
return ans
n = int(input())
s = {x for x in range(n)} # set = {0,1,2,3... n - 1}
arr = [-1] * n
print(rec(0, n))