N-Queen
문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
코드
풀이 과정
N X N 크기의 체스판에 서로 겹치지 않게 N개의 퀸을 놓을 수 있는 경우의 수를 출력하는 문제이며 백트래킹 알고리즘의 가장 대표적인 문제다.
한 열당 퀸을 1개씩 놓을 수 있다. 그러므로 퀸을 1열부터 N열까지 놓는다고 생각하면 i열에 있는 퀸의 행의 값을 row[i]로 표현할 수 있다.
dfs 알고리즘을 수행하는데, 처음 if 문은 무한루프를 탈출하기 위한 기능이고 한정 함수의 조건을 만족하면 재귀함수로 들어가게 된다. 재귀함수는 다음 열로 계속 진행시켜 주는 것이고 for j in range(N) 부분은 행을 다음 행으로 계속 진행시켜 주는 것이다.
풀이
# 퀸 놓아보기 함수
def build_queen(n, N) :
global result # 글로벌로 생성
# 재귀 빠져나가기
if n == N :
result += 1
return
# 재귀 빠져나갈 수 없을 때 퀸을 놓아보고 이전 퀸들과 비교.
else :
for i in range(N) :
row[n] = i
# for문이 break 걸리지 않고 다 돌면 else(재귀) 실행
for j in range(n):
# 한 열에 하나씩 들어가므로 열 바교는 필요없다.
# 또한 대각선은 수학식을 생각해보면 쉽게 구할 수 있다.
if row[j] == row[n] or (row[n] - n) == (row[j] - j) or (row[n] + n) == (row[j] + j):
break
else : build_queen(n+1, N)
# 입력
s = int(input())
# 초기값 설정
result = 0
row = [300] * s
# 퀸 놓아보기 함수
build_queen(0, s)
# 출력
print(result)
네~