문제 접근
'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';
}
결과
'개발 > 알고리즘' 카테고리의 다른 글
백준 13549번 : 숨바꼭질3 (0) | 2020.10.11 |
---|---|
백준 12865번 : 평범한 배낭 (0) | 2020.10.11 |
Codeforce Round #674 (Div.3) Virtual Participation 리뷰 (0) | 2020.10.04 |
백준 4358번 : 생태학 (0) | 2020.09.27 |
백준 5052번 : 전화번호 목록 (0) | 2020.09.25 |