-
Notifications
You must be signed in to change notification settings - Fork 0
/
boj_9663.py
69 lines (56 loc) · 1.26 KB
/
boj_9663.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
# !/usr/bin/env python
# -*- coding: utf-8 -*-
# boj 9663 N-Queen
N = int(input())
board = [[0] * N for _ in range(N)]
count = 0
def backtracking(n):
global count
if n == N:
count += 1
return
for j in range(N):
if is_possible(n, j):
backtracking(n + 1)
board[n][j] = 0 # 이전 상태로 돌아가기
def is_possible(r, c):
"""
# i, j에 Queen을 놓을 수 있는지 확인하는 함수
"""
# 가로 확인
if 1 in board[r]:
return False
# 세로 확인
for i in range(len(board)):
if board[i][c] == 1:
return False
# 우하향 대각선 확인
i, j = r, c
while i > -1 and j > -1:
if board[i][j] == 1:
return False
i -= 1
j -= 1
i, j = r, c
while i < N and j < N:
if board[i][j] == 1:
return False
i += 1
j += 1
# 우상향 대각선 확인
i, j = r, c
while i > -1 and j < N:
if board[i][j] == 1:
return False
i -= 1
j += 1
i, j = r, c
while i < N and j > -1:
if board[i][j] == 1:
return False
i += 1
j -= 1
board[r][c] = 1
return True
backtracking(0)
print(count)