input :
- n
output :
- 놓을 수 있는 Queen의 위치를 다 표시하시오.
조건 :
- 1 <= n <= 9
Solution explain : Solution1
idea
- 재귀적으로 해결할 수 있을까?
- 만약 위치를 지정하고 8방향을 다 확인하려고 한다면 쉽게 생각해보아도 81 (평균적으로 놓을 수 있을 장소 50) (약 24) * ~~~ 하면 일단 너무 크다.
- row를 구별하면서 본인 row 기준 위에 존재하는 기물을 확인한다고 하면 확인해야 하는 위치가 기하급수적으로 줄어든다.
- 각 row에서 놓을 수 있는 위치는 최대 9자리. (확인해야 하는 위치는 최대 27개이다.)
- 이렇게 해도 왜 시간 복잡도에 안 걸리는 지는 모르겠는데... 모르겠다.
- 그렇게 해서 특정 row의 칼럼에 놓아보면서 가능성을 확인한다.
- 위로 볼 때는 대각선 2방향, 그리고 위의 칼럼에 기물이 존재하는지 본다.
- queens 배열의 경우 idx가 row의 값을, value가 col의 값을 저장하는 형태이다.
주의
- 비트 마스크로 하는 건... 손대지 말자 복잡하다.
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
ret = []
dx = [-1, -1, -1]
dy = [0, 1, -1]
def valid(queens, x, y):
for i in range(3):
nx, ny = x + dx[i], y + dy[i]
while 0 <= nx < n and 0 <= ny < n:
if ny == queens[nx]:
return False
nx, ny = nx + dx[i], ny + dy[i]
return True
def recursive(queens, idx):
if idx == n:
temp_ret = []
for i in range(n):
temp = ["."] * n
ny = queens[i]
temp[ny] = "Q"
temp_ret.append("".join(temp))
ret.append(temp_ret)
return
for i in range(n):
if valid(queens, idx, i):
queens[idx] = i
recursive(queens, idx + 1)
queens[idx] = -1
recursive([-1] * n, 0)
return ret