문제:
가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.
예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.
체스판의 가로 세로의 길이 n이 매개변수로 주어질 때 , n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution 함수를 완성해주세요.
풀이 방법:
되추적 방법을 사용하는 대표적인 예시인 문제이다. 따라서 queens에서는 각 col별로 queen을 배치하는데 우선 promising이라는 함수에서 이전에 배치한 col을 기준으로 해당 인덱스에 queen을 배치할 수 있는지 판단해준다. 모든 방법을 다 판별해주는 방법도 생각할 수 있지만 그럴 경우 n이 커짐에 따라 많은 시간이 발생할 것이다. 따라서 promising이라는 되추적 판단을 해주는 함수로 인해서 많은 시간을 단축 할 수 있었다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
def promising(i,col):
k=0
correct=True
while (k<i and correct):
if (col[i]==col[k] or abs(col[i]-col[k])==i-k):
correct=False
break
k+=1
return correct
def queens(n,i,col,count):
if (promising(i,col)):
if (i==n-1):
count.append(col)
else:
for j in range(n):
col[i+1]=j
queens(n,i+1,col,count)
def solution(n):
col=n*[0]
global count
count=[]
queens(n,-1,col,count)
return len(count)
|
cs |
문제 링크:
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]9935. 문자열 폭발 (0) | 2019.08.29 |
|---|---|
| [BOJ]1120. 문자열 (0) | 2019.08.28 |
| [BOJ]9465. 스티커 (0) | 2019.08.24 |
| [BOJ]1406. 에디터 (0) | 2019.08.23 |
| [BOJ]11053. 가장 긴 증가하는 부분 수열 (0) | 2019.08.22 |