백준 9663번 : N-Queen

문제 접근

---

'Queen을 한 줄에 하나밖에 배치하지 못한다.'는 점을 이용하여 풀었다. 우선 NxN 크기의 Board 배열을 만들어 놓고, 모든 열에 대해 Queen을 놓을 수 있는 위치에 하나를 배치하고, 그다음 줄을 확인한다. line 이 N까지 가면 N 개를 배치한 것이므로 1을 반환하고, line-1 번째 줄로 돌아가도록 구현했다.

 

처음에는 board 에 Queen을 배치할 때 안 되는 부분을 1 증가시키는 방식으로 풀이했는데, 풀고 나니 더 깔끔한 풀이들이 보였다. 첫 번째는 Queen 이 배치되면 대각선 2개, 세로줄, 가로줄 전체가 안 되는 것이므로 크기 N*2 배열을 2개 만들어 대각선까지 한 번에 처리하는 것이고, 두 번째는 이전 줄에서 Queen 이 놓인 위치를 통해 해당 위치가 안 되는지 그때그때 판단해보는 것이다. 두 번째 풀이가 깔끔해 보여서 참고하여 다시 구현해봤다.

 

 

문제 코드 ( 기존 )

---

#include <iostream>

using namespace std;

int board[16][16] = {0,};
int N;

void setQueen(int x, int y)
{
	for(int i=1; i<=N; ++i)
	{
		++board[i][y];
		++board[x][i];
		
		if(y+i <= N)
			++board[x+i][y+i];
		if(y-i > 0)
			++board[x+i][y-i];
	}
	
	--board[x][y];
}

void delQueen(int x, int y)
{
	for(int i=1; i<=N; ++i)
	{
		--board[i][y];
		--board[x][i];
		
		if(y+i <= N)
			--board[x+i][y+i];
		if(y-i > 0)
			--board[x+i][y-i];
	}
	
	++board[x][y];
}

int count(int line)
{
	int ans=0;
	
	if(line == N)
		return 1;
	
	for(int i=1; i<=N; ++i)
		if(!board[line+1][i])
		{
			setQueen(line+1, i);
			ans += count(line+1);
			delQueen(line+1, i);
		}
	
	return ans;
}

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>N;
	cout<<count(0)<<'\n';
}

 

 

문제 코드 ( 새 방법 )

---

#include <iostream>

using namespace std;

int N;
int board[16];

int count(int line)
{
	if(line == N)
		return 1;
	
	int ans=0;
	
	for(int i=0; i<N; ++i)
	{
		bool flag=false;
		
		for(int j=0; j<line; ++j)
			if(board[j] == i || board[j] - (line-j) == i || board[j] + (line-j) == i)
			{
				flag = true;
				break;
			}
		
		if(!flag)
		{
			board[line] = i;
			ans += count(line+1);
		}
	}
	
	return ans;
}

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>N;
	cout<<count(0)<<'\n';
}

 

결과

---