백준 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++ 해줍니다.

	#include <bits/stdc++.h>
	using namespace std;
	int N, arr[16][16], ans;
	// (a,b) 위치에서 위, 왼쪽대각선, 오른쪽 대각선 확인
	bool Ch(int a, int b){
	int x = a;
	int y = b;
	// column 바로 위
	while(x>0){
	x--;
	if(arr[x][y]==1) return false;
	}
	x = a;
	y = b;
	// 왼쪽 대각선 위
	while(x>0 && y>0){
	x--;
	y--;
	if(arr[x][y]==1) return false;
	}
	// 오른족 대각선 위
	x = a;
	y = b;
	while(x>0&&y<N){
	x--;
	y++;
	if(arr[x][y]==1) return false;
	}
	return true;
	}
	// x번째 row에 놓을 수 있는 column 이 있으면 놓아본다.
	void DFS(int row){
	// 0~N-1 모든 row에 다 놓았다면 ans++
	if(row>=N){
	ans++;
	return;
	}
	for (int i = 0; i < N; ++i){
	// x번째 row의 0~N-1 column중 놓을 수 있는경우
	if(Ch(row,i)){
	arr[row][i]=1;
	DFS(row+1);
	arr[row][i]=0;
	}
	}
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	DFS(0);
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 9663.cpp hosted with ❤ by GitHub