백준 #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)