Programming/Programmers
[프로그래머스] N-Queen (Python)
데이터현
2021. 11. 23. 20:33
https://programmers.co.kr/learn/courses/30/lessons/12952
코딩테스트 연습 - N-Queen
가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은
programmers.co.kr
다른 풀이를 참고했다. 아직 dfs를 짜는데 좀 익숙하지 않은 것 같다.
나중에 다시 살펴봐야겠다.
import sys
sys.setrecursionlimit(10**6)
def dfs(queen,n,row):
answer = 0
if n == row:
return 1
for i in range(n):
queen[row] = i
for j in range(row):
if queen[j] == queen[row]:
# 같은 열에 있을 경우
break
if abs(queen[j] - queen[row]) == row-j:
# 대각선인 경우
break
else:
answer += dfs(queen,n,row+1)
return answer
def solution(n):
queen = [0]*n
answer = dfs(queen,n,0)
return answer