[Algorithm] 백준 9663번 N-Queen(파이썬)
백준 #9663
문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입출력 규칙
1. 입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
2. 출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
문제접근
이번 문제는 백트래킹의 대표적인 문제인 N-Queen문제이다.
한열에 퀸은 한개씩 놓을 수 있으며, 각 행마다 반드시 1개의 퀸이 존재해야한다. 체스의 퀸이 공격하는 범위를 보자면 1칸의 범위내에는 모두 공격이 가능하고, 모든 대각선으로 공격이 가능하므로 상하좌우 및 대각선 방향으로 겹치지 않게 동선을 구성하면 된다. dfs 알고리즘과 재귀함수를 이용해 문제를 접근하여 풀어보면 된다.
문제풀이(Python)
def queen(n, N) :
global result
if n == N :
result += 1
return
else :
for i in range(N) :
row[n] = i
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 : queen(n+1, N)
s = int(input())
result = 0
row = [300] * s
queen(0, s)
print(result)
Author And Source
이 문제에 관하여([Algorithm] 백준 9663번 N-Queen(파이썬)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@goplanit/Algorithm-백준-9663번-N-Queen파이썬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)