[백준 - 9663] N-Queen

#include <iostream>

#define MAX 50
using namespace std;

int N;
int result = 0;
//b는 인덱스는 각 열의 위치를 의미한다.
//값은 이 열에 놓였는지를 뜻한다. true면 놓여있는 것
bool b1[MAX];
//값은 대각선'/'의 판별 식은 a + i
bool b2[MAX];
//값은 대각선'\'의 판별 식은 a - i + n //n을 더해주는것은 음수가 나오지 않게 하기 위해
bool b3[MAX];

void Solve(const int  & a)
{
	if (a == N)
	{
		result++;
		return;
	}

	//i가 어느 열위치에 놓이려고 하는지를 뜻함
	for (int i = 0; i < N; ++i)
	{
		if (b1[i] == true || b2[a + i] == true || b3[a - i + N] == true) continue;

		b1[i] = true;
		b2[a + i] = true;
		b3[a - i + N] = true;
		Solve(a + 1);
		b1[i] = false;
		b2[a + i] = false;
		b3[a - i + N] = false;
	}
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N;
	Solve(0);
	cout << result;
	return 0;
}

---

||사고 과정

연습하고 있는 백트래킹의 문제

처음에는 중복될수 있는게 많지 않을까? ,중복처리 다 할 수 없을거 같은데? 라는 생각으로 포기할뻔했다.

근데 몇가지 케이스를 직접 그리면서 해보니까 맨 위의 행을 반복하면 중복될 수가 없었다.

역시 뭐든 막연하면 한번 직접해봐야한다.. 안 했으면 포기했을뻔 했다.

 

암튼 그래서 한 행씩 내려오면서 검사를 하는데

여태 두었던 모든 퀸들의 열과 대각선을 검사해야할까? 해서 한 5까지는 시도해본결과

열은 다 검사하되 대각선은 바로 위의 퀸에만 검사해도 답이 나왔다.

하지만 이건 완전 잘못된 선택..

단지 맵이 작아서 우연히 맞았을 뿐이고 맵이커지면 규칙에 어긋난 배치도 카운팅 됐다.

이렇게 정확히 모를때는 한가지경우라도 범위가 큰 케이스에서 시도를 해보자

 

결국 한시간이 지나고 다른 사람의 코드를 보았다..

대각선 판별을 깔끔하게 하는걸 보고 놀랐다..

이건 잘 기억해 두어야겠다.

---

||사용 기법

• Back tracking 

---

||새로 알게 된것

• 대각선 판별

하나의 대각선' / ' 에 속하는 좌표는 X + Y값이 같다!

그 역 대각선은 X - Y 의 값이 같다!

단 X -Y 는 음수가 나올 수 있기에 배열에 대입하는 경우에는 고정 값을 더해주어야한다

뭔가 알게돼서 넘 좋았다ㅋㅋ