[백준] No.9663 - N-Queen (C++)

문제

https://www.acmicpc.net/problem/9663

9663번: N-Queen

풀이

bool board[14][14] : 퀸을 놓기가 가능하면 true로 저장해 둠.

 

void BanBoard(int r,int c) : r과 c 위치에 퀸을 둘 경우 양대각과 가로 세로의 board를 false로 변경

 

voidDfs(int column): column이 N이상일 경우만 cnt를 +1하고 나머지에서는 퀸을 하나씩 두며 Dfs 재귀 호출

board_copy를 선언해 이전의 board의 값을 저장해 두고 column의 row값을 for문으로 돈다.

만약 퀸을 두는 것이 가능하면 BanBoard를 호출 후 Dfs(column+1)를 재귀 호출해 다음 column에서 가능한 수를 찾는다.

후출 후 돌아온다면 이전의 board값으로 복구시키기 위해 copy_board값을 다시 넣어준다. 

 

소스코드

	//https://www.acmicpc.net/problem/9663
	#include <iostream>
	#include <string.h>
	using namespace std;
	int N;
	int cnt =0;
	bool board[14][14]; //체스를 놓기가 가능한지의 여부
	void BanBoard(int r,int c){
	int i=0;
	for(i=0; i<N ;++i ){
	board[i][c] = false;
	}
	for(i=0; i<N ;++i ){
	board[r][i] = false;
	}
	int nr=r;
	int nc = c;
	while(1){
	--nr;
	--nc;
	if(0 <= nr && 0<= nc)
	board[nr][nc] = false;
	else
	break;
	}
	nr=r;
	nc=c;
	while(1){
	++nr;
	++nc;
	if(nr<N && nc<N)
	board[nr][nc] = false;
	else
	break;
	}
	nr=r;
	nc=c;
	while(1){
	--nr;
	++nc;
	if(0 <= nr && nc<N)
	board[nr][nc] = false;
	else
	break;
	}
	nr=r;
	nc=c;
	while(1){
	++nr;
	--nc;
	if(nr<N && 0<=nc)
	board[nr][nc] = false;
	else
	break;
	}
	}
	void Dfs(int column){
	if(column >= N){
	++cnt;
	return;
	}
	bool board_copy[14][14];
	for(int i=0; i<N ; ++i)
	for(int j=0; j<N ; ++j)
	board_copy[i][j] = board[i][j];
	for(int i=0; i<N ; ++i){
	if(board[i][column]){
	BanBoard(i, column);
	Dfs(column+1);
	for(int i=0; i<N ; ++i)
	for(int j=0; j<N ; ++j)
	board[i][j] = board_copy[i][j];
	}
	}
	}
	int main() {
	cin>> N;
	memset(board, true, sizeof(board));
	Dfs(0);
	cout<<cnt<<'\n';
	return 0;
	}

view raw N-Queen.cpp hosted with ❤ by GitHub

복기

if(column >= N) 부분에서 N-1과 비교해 한참을 헤맸다..