가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.
제한사항
- 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
- n은 12이하의 자연수 입니다.
사실 처음에는 풀이방식 보고도 이해가 안 갔다.
스스로 이해한 걸 정리하는 의미에서 선 코드 투척 후 알고리즘을 설명해보려 한다.
ans = 0
def check(queens, row):
for i in range(row):
if queens[i] == queens[row] or abs(queens[i] - queens[row]) == row - i:
return False
return True
def search(queens, row):
n = len(queens)
global ans
if row == n:
ans += 1
else:
for col in range(n):
queens[row] = col
if check(queens, row):
search(queens, row + 1)
def solution(n):
search([0] * n, 0)
return ans매개변수 queens는 퀸의 위치 정보를 담은 배열이다.
각 row 당 하나의 queen이 배치된다는 사실을 이용해서, 각 row 별로 queen이 몇번째 column에 위치했는지를 알 수 있다.
그 다음에 queens의 위치 선정을 진행하는 search 함수를 보자.
만약 현재 row가 n이 된다면 하나의 체스판에 queen에 배치하는 게 끝난 셈이다. 그러므로 ans에 1을 더한다.
for col in range(n):
queens[row] = col
if check(queens, row):
search(queens, row + 1)일단 퀸을 [row, col]에 둔다.
그러고 해당 위치에 두는 게 가능한지 확인한다.
가능하다면 다음 줄에 가서 search를 계속 한다.
check 함수를 한번 살펴 보자면,
def check(queens, row):
for i in range(row):
if queens[i] == queens[row] or abs(queens[i] - queens[row]) == row - i:
return False
return True세로줄이랑 대각선에 퀸을 둘 수 있는지 확인하는 함수다.
queens[row]로 접근하면 몇번째 column에 퀸을 둔건지 알 수 있다.
1. queens[i] == queens[row]는 column 값이 같은지 확인하는 것이고 (세로줄 확인)
2. 가로차 == 세로차이면 같은 대각선 상에 존재하는 것이므로 다음과 같이 확인하는 것이다.
👉abs(queens[i] - queens[row]) == row - i
