N-Queen

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

나에게는 숙적 같은 문제였는데 해결하게 돼서 기쁘다
C언어로 풀 때는 이차원배열을 복사해서 풀었는데
한줄에 퀸이 하나씩만 올 수 있다는 것을 이용해 N칸의 일차원 배열에 각 row의 퀸의 위치 col을 저장하여 풀었다.

1. cnt를 매개변수로 넣어 cnt를 세는 법

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))

또는

2. 전역변수를 이용하여 cnt를 세는 방법

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))