🔥

문제

체스라는 게임에서 퀸은 가장 강력한 말로, 가로, 세로, 대각선을 모두 이동할 수 있다.

N * N 크기에 체스 판에 서로를 잡을 수 없도록 퀸을 배치할 때, 최대 N개의 퀸을 배치할 수 있다.

그런데, N이 6보다 큰 경우에는 N개의 퀸을 배치하는 방법이 유일하지는 않다.

N이 주어질 때, N개의 퀸을 배치할 수 있는 방법의 개수를 출력해보자.

입력

체스판의 크기 N이 주어진다.(단, N은 5이상 13이하이다)

출력

퀸을 배치하는 경우의 수를 출력합니다.

예제 1 입력

5

예제 1 출력

10

예제 2 입력

6

예제 2 출력

4

Source

  1. 정석 방법(파이썬 기준 시간초과)
n = int(input())
ans = 0
arr = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

def dfs(x):
	global ans

	if(x == n + 1):
		ans += 1
		return
	for i in range(1, n + 1):
		pos = True
		for j in range(1, x):
			if(i == arr[j] or j + arr[j] == x + i or
			  j - arr[j] == x - i):
				pos = False

		if(pos):
			arr[x] = i
			dfs(x + 1)
			arr[x] = 0

dfs(1)
print(ans)
  1. 반복문으로 공격가능한 퀸이 있는지 확인하는 방법
n = int(input())
board = [[0 for _ in range(n)] for _ in range(n)]
check = [[0 for _ in range(n)] for _ in range(n)]
count = 0

def dfs(k):
    global count

    if(k == n):
        count += 1
        return

    for i in range(n):
        if(check[k][i] > 0):
            continue
        # j: 아래로의 변화량
        for j in range(n):
            if(k + j >= n):
                break
            check[k + j][i] += 1 # 같은 열 체크
            # 왼쪽 위 체크
            if(i - j >= 0):
                check[k + j][i - j] += 1
            # 오른쪽 위 체크
            if(i + j < n):
                check[k + j][i + j] += 1

        dfs(k + 1)

        for j in range(n):
            if(k + j >= n):
                break
            check[k + j][i] -= 1
            if(i - j >= 0):
                check[k + j][i - j] -= 1
            if(i + j < n):
                check[k + j][i + j] -= 1

dfs(0)
print(count)

참고