문제 설명
백트래킹을 이용하여 대각선으로 이동이 가능한 비숍을 부딪히지 않게 배치하는 문제이다.
그냥 풀게되면 시간초과가 발생하게 되는데, 체스판의 하얀 부분과 까만 부분에 두는 비숍은 어떻게 두더라도 둘이 부딪힐 일이 없다는 것을 이용하여 둘을 아예 분리해서 풀어야 시간초과가 나지 않는다.
풀이
int check(int x,int y,int a,int b){
if(abs(x-a)==abs(y-b)){
return 0;
}else{
return 1;
}
}대각선에 겹치는지 검사할 때는 둘의 가로끼리 세로끼리 더하여 절댓값이 같은지 검사한다.
void back(int x,int y){
int j=y;
if(num%2==1&&y==num+1){
x=x+1;
j=1;
}else if(num%2==0){
if(y==num+1){
x=x+1;
j=0;
}else if(y==num){
x=x+1;
j=1;
}
}
if(v.size()>maxx){
maxx=v.size();
}
for(int i=x;i<num;i++){
for(j;j<num;j+=2){
if(map[i][j]==1){
c=0;
for(int k=0;k<v.size();k++){
if(!check(i,j,v[k].first,v[k].second)){
c=1;
break;
}
}
if(c==0){
map[i][j]=2;
v.push_back(make_pair(i,j));
back(i,j+2);
v.pop_back();
map[i][j]=1;
}
}
}
if(num%2==0){
if(j==num+1){
j=0;
}else{
j=1;
}
}else{
if(j==num+1){
j=1;
}else{
j=0;
}
}
}
}백트래킹을 하는 함수 위와 똑같은 것을 두개 만들어줬다.
아까 설명했듯 검은 부분과 하얀 부분의 max값을 따로 구해줘야하기 때문이다.
여기서 오류가 나서 오류를 찾는데 시간이 걸렸었는데
체스판을 두개씩 건너뛸 때 다음줄로 넘어가는 처리를 판의 한 변이 홀수일때와 짝수일때를 나누어서 판단을 하지 않았기 때문이였다.
(그림에서와 같이 판의 한변의 길이가 홀수일때, j+2==num일때는 다음 줄에서 j=0으로 해주었고 j+2==num+1일때는 다음줄 j=1로 해주었다.
한 변의 길이가 짝수일때는 반대로 j+2==num일때 다음줄 j=1,
num+1일때는 j=0으로 해준다.)
- 빨간색 - 홀수일 때
- 노란색 - 짝수일 때
코드
#include <stdio.h>
#include <vector>
using namespace std;
int map[11][11];
vector<pair<int,int> > v;
int num;
int abs(int x){
if(x<0){
return -x;
}else{
return x;
}
}
int check(int x,int y,int a,int b){
if(abs(x-a)==abs(y-b)){
return 0;
}else{
return 1;
}
}
int c=0;
int maxx=0;
int maxx2=0;
void back(int x,int y){
int j=y;
if(num%2==1&&y==num+1){
x=x+1;
j=1;
}else if(num%2==0){
if(y==num+1){
x=x+1;
j=0;
}else if(y==num){
x=x+1;
j=1;
}
}
if(v.size()>maxx){
maxx=v.size();
// for(int i=0;i<num;i++){
// for(int j=0;j<num;j++){
// printf("%d ",map[i][j]);
// }
// printf("\n");
// }
// printf("\n");
}
for(int i=x;i<num;i++){
for(j;j<num;j+=2){
if(map[i][j]==1){
c=0;
for(int k=0;k<v.size();k++){
if(!check(i,j,v[k].first,v[k].second)){
c=1;
break;
}
}
if(c==0){
map[i][j]=2;
v.push_back(make_pair(i,j));
back(i,j+2);
v.pop_back();
map[i][j]=1;
}
}
}
if(num%2==0){
if(j==num+1){
j=0;
}else{
j=1;
}
}else{
if(j==num+1){
j=1;
}else{
j=0;
}
}
}
}
void back2(int x,int y){
int j=y;
if(num%2==1&&y==num+1){
x=x+1;
j=1;
}else if(num%2==0){
if(y==num+1){
x=x+1;
j=0;
}else if(y==num){
x=x+1;
j=1;
}
}
if(v.size()>maxx2){
maxx2=v.size();
// for(int i=0;i<num;i++){
// for(int j=0;j<num;j++){
// printf("%d ",map[i][j]);
// }
// printf("\n");
// }
// printf("\n");
}
for(int i=x;i<num;i++){
for(j;j<num;j+=2){
if(map[i][j]==1){
c=0;
for(int k=0;k<v.size();k++){
if(!check(i,j,v[k].first,v[k].second)){
c=1;
break;
}
}
if(c==0){
map[i][j]=2;
v.push_back(make_pair(i,j));
back2(i,j+2);
v.pop_back();
map[i][j]=1;
}
}
}
if(num%2==0){
if(j==num+1){
j=0;
}else{
j=1;
}
}else{
if(j==num+1){
j=1;
}else{
j=0;
}
}
}
}
int main(){
scanf("%d",&num);
for(int i=0;i<num;i++){
for(int j=0;j<num;j++){
scanf("%d",&map[i][j]);
}
}
back(0,0);
v.clear();
// printf("max2\n");
back2(0,1);
// printf("%d %d ",maxx,maxx2);
printf("%d",maxx+maxx2);
}