파이썬으로 풀어보는 백준 9663번: N-Queen

Python/문제풀이

by 코딩하는 낙타 2020. 1. 15. 23:29

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

9663번: N-Queen

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

내 풀이:

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

N = int(input())
 
row = [100] * N
check = [False] * (N+1)
result = 0
 
 
 
def checking(index, i):
 
    for j in range(index):
        if abs(row[j] - i) == abs(j - index):
 
            return True
 
def play(index, N):
    global result
    if index == N:
        result += 1
        return
 
    for i in range(1, N+1):
        if check[i]:
            continue
        elif checking(index, i):
            continue
 
        check[i] = True
        row[index] = i
        play(index+1, N)
        check[i] = False
 
play(0, N)
print(result)

 

시간초과

다른 풀이 방법을 생각해봐야 할 것 같다.

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

N = int(input())
row = [100] * N
check = [False] * (N+1)
result = 0
 
 
def checking(index, i):
 
    for j in range(index):
        if abs(row[j] - i) == abs(j - index):
 
            return True
 
 
def play(index, N):
    global result
    if index == N:
        result += 1
        return
 
    for i in range(1, N+1):
        if check[i]:
            continue
        elif checking(index, i):
 
            continue
 
        check[i] = True
        row[index] = i
        play(index+1, N)
        check[i] = False
 
 
play(0, N)
print(result)

 

PyPy3, 13960ms

'Python > 문제풀이' 카테고리의 다른 글

[SW Expert Academy] 5550. 나는 개구리로소이다 (0)	2020.01.18
백준 2108번: 통계학 (0)	2020.01.17
파이썬으로 풀어보는 백준 15649번 N과 M (0)	2020.01.15
파이썬으로 풀어보는 백준 11650번, 11651번: 좌표 정렬하기 (0)	2020.01.15
(Python) 문자열에서 모음 지우기 (0)	2020.01.14