글 읽기 - n-queen 코드좀 봐주실수 있을까요

p_ce1052 3년 전 0

한 줄에 하나씩 퀸을 세우고 y를 늘려가면서 재귀호출합니다. 퀸 하나를 새로 새우면 해당 세로줄은 쓸 수 없으므로 col[x] = true로 해줍니다. 또한 새로 퀸을 세우면서 대각선 칸들에 공격표시를 해줍니다. 그래서 다음 퀸을 세울 때는 col[x] = false인 곳에만 세우고, 공격받는 지점에서는 그냥 return 합니다. 테스트 케이스도 제대로 나오지가 않는데 어디가 문제일까요?

#include<iostream>
#include<vector>
using namespace std;

int n;
bool map[16][16];
bool col[16];
int total=0;

void attackORnot(int x,int y, bool attack){ //대각선 방향 표시  
	int tempx = x; 
	int tempy = y;
	while(y<=n && x<=n && x>=1){ //왼쪽 아래 대각선  
		map[y][x] = attack;
		y++;
		x--;
	}
	while(tempy<=n && tempx<=n && tempx>=1){ //오른쪽 아래 대각선 
		map[tempy][tempx] = attack;
		tempy++;
		tempx++;
	}
}
void back_tracking(int x,int y){
	if(map[y][x]) return; //다른 퀸들에게 공격 받는 지점이면 돌아간다 
	if(y==n){ //공격받는 지점이 아니고 n번째 퀸을 놓을 수 있다면  카운트하고 돌아간다
		total++;
		return;
	}
	col[x] = true; //x에 세웠다고 표시
	attackORnot(x,y,true); //대각선에 표시 
	for(int i=1; i<=n; i++){
		if(!col[i]) back_tracking(i,y+1); //아직 점령되지 않은 세로칸에 세운다  
	} 
	col[x] = false;
	attackORnot(x,y,false); //표시한거 지우기  
}
int main(){
	cin>>n;
	for(int i=1; i<=n; i++) back_tracking(i,1);
	cout<<total;
}

kcan1416 3년 전 1

먼저 둔 퀸이 색칠한 곳과 지금 둔 퀸이 색칠한 곳이 겹치는 부분에서는 색칠을 지우지 말아야 합니다

p_ce1052 3년 전 0

색칠을 항상 아래로만 해나가고 겹치는 곳에는 퀸을 두지 않기 때문에 애초에 겹치는 부분에는 색칠을 하지 않는다고 생각했는데 답이 이상하게 많이 나오긴 하더라구요 어느 줄이 잘못됬는지 알 수 있을까요?

p_ce1052 3년 전 0

무슨말씀하시는지 이해됬습니다 감사합니다 공격 지점은 겹칠 수가 있겠군요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

n-queen 코드좀 봐주실수 있을까요

p_ce1052 3년 전 0

kcan1416 3년 전 1

p_ce1052 3년 전 0

p_ce1052 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말