백준 9663번 N-Queen

< 백준 9663번 N-Queen - 마포 코딩박 >

사용한 알고리즘: DFS


 N*N grid의 각 row에 퀸을 하나씩 놓을 수 있는 배치 수를 구하는 문제였습니다.
 DFS 탐색을 통한 완전탐색으로 문제를 해결하였습니다.

문제풀이는 다음과 같습니다.
(1) (코드: arr[16][16])
 퀸을 놓으면 1, 비어있으면 0 으로 저장할 배열 하나를 만듭니다.

(2) (코드: 6~31)
 어떤 위치 (a,b) 에 퀸을 배치할 수 있는지 여부를 확인할 함수를 만듭니다.
 과정 (3) 에서 퀸은 위 row부터 아래로 차례로 배치할 것이므로, 해당 위치의 위, 왼쪽대각선위, 오른쪽 대각선위 에 먼저 놓인 퀸이 있는지만 체크해주면 됩니다.

(3)
 기본적으로 한 줄(row)에는 하나의 퀸을 놓을 수 있습니다.
 0번째 row 에서 N-1 row 까지 퀸을 하나씩 배치 할 수 있으면 해당 배치를 1개의 가능배치로 세줄것입니다.
 x번째 row 의 0~N-1 column (= (x,0)~(x,N-1) ) 을 과정 (2)에 만들어놓은 함수로 퀸을 놓을 수 있는지 확인합니다. 놓을 수 없다면 무시하고, 놓을 수 있는 칸이 있으면
 1. 해당칸에 놓고 x+1 row로 재귀
 2. 해당칸에 놓지않고 x row의 나머지 column 확인
 마지막 N-1 row 에 놓을 수 있으면 ans++ 해줍니다.