소스코드
import sys
input = sys.stdin.readline
N = int(input().strip())
pos = [0] * N # pos[i] = j 라면, 이는 i행j열에 퀸이 있음을 의미
result = 0 # 총 경우의 수
def position_check(row):
# 인자로 넘어온 row(행) 이전까지의 퀸 정보를 기반으로 퀸을 둘 수 있는 포지션인지 확인
for i in range(row):
if pos[i] == pos[row] or abs(pos[i] - pos[row]) == abs(i-row):
return False
return True
def solve(row_depth):
if row_depth == N:
result += 1
return
for col in range(N):
pos[row_depth] = col # 해당 행의 열 위치를 모두 확인
if position_check(row_depth) == True:
solve(row_depth+1) # 재귀함수 실행
solve(0)
sys.stdout.write(f"{result}\n")
Python
복사
풀이
핵심 논리
•
1행부터 차례대로 다음 행으로 이동
•
다음 행에서 모든 열들을 확인
◦
이때, 두 가지를 확인해야한다
1.
대각선인지
2.
같은 열에 있는지
◦
만약 해당 열에 배치가 가능하다면, 이 정보를 가지고 재귀함수를 실행 → 다음 행으로
왜 재귀함수를 사용했나요?
제가 재귀를 사용한 이유는 다음과 같습니다 :
행마다 동일한 로직을 수행한다
재귀함수의 인자로 행 정보를 넘겨주는 이유는?
재귀함수는 내부에서 재귀적으로 실행되기 이전의 정보를 가지고 다음 함수를 실행합니다. 재귀함수는 종료 조건을 작성하는 게 중요한 부분 중 하나인데, 이때 행 정보를 이용해서 N과 동일할 경우 경우의 수를 증가시켜주면 되겠다는 생각을 했습니다.