문제 설명
가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.
예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.
체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.
제한사항
- 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
- n은 12이하의 자연수 입니다.
입출력 예
| n | result |
|---|---|
| 4 | 2 |
내 코드
def n_queen(n, x, queen):
res = 0
if x == n: #재귀 빠져나가기
return 1
for i in range(n):
queen[x] = i
if check(x, queen):
res += n_queen(n, x+1, queen)
return res
def check(x, queen):
for i in range(x):
if queen[x] == queen[i] or abs(x-i) == abs(queen[x] - queen[i]):
return False
return True
def solution(n):
queen = [0] * n
answer = n_queen(n, 0, queen)
return answer풀이
대표적인 백트래킹 문제
첫번째로는 queen 배열에서 queen의 행과 열의 정의가 요구된다.
n의 크기만큼 queen 배열의 size를 잡으면 queen[i]는 queen 2차원 배열에 할당된 queen의 위치라고 볼 수 있고, i는 그 위치한 queen의 행이라고 볼 수 있다.
두번째로는 queen이 서로 마주하면 안되는 조건을 check해야한다.
이를 check() 함수로 정의할 것이다.
- 퀸은 동일한 열에 위치하면 안된다.
abs(x-i)==abs(queen[x] - queen[i]): 대각선 방향 확인
