[백준]Baekjoon9663(백트래킹)

문제링크 : https://www.acmicpc.net/problem/9663

풀이

재귀를 통해 가능한 모든 부분을 탐색하였다.

int queen(int rows)

위와같이 줄 번호를 매개변수로 받는 함수를 통해 문제를 풀었다.

해당 행이 주어졌을 때 모든 열을 탐색하면서 만약 대각선, 세로에 다른 퀸이 서있지 않다면

bool형 배열에 그것을 체크한 뒤 

result += queen(rows+1)을 하도록 했다.

이 함수는 rows = n이 됐을 때 (주어진 행을 모두 검사하고 초과된 경우)

1을 return하며 그렇지 않은 경우에는 result를 return하도록 하였다.

대각선을 검사하는 방식은 다음과 같이 하였다.

오른쪽 위에서 왼쪽 밑으로 향하는 대각선의 경우 행과 열의 index를 더해보면 다음과 같다.

   0 1 2 3 4

0 0 1 2 3 4

1 1 2 3 4 5

2 2 3 4 5 6

3 3 4 5 6 7

4 4 5 6 7 8

0 부터 (n-1) + (n-1) 까지 대각선끼리 같은 숫자를 가짐을 확인할 수 있다.

왼쪽 위에서 오른쪽 밑으로 향하는 대각선의 경우 행과 열의 index를 빼 보았다.

      0   1   2   3   4

  0  0   -1  -2  -3 -4

  1  1   0   -1  -2 -3

  2  2   1   0   -1 -2

  3  3   2   1    0 -1

  4  4   3   2    1  0

이 역시 대각선끼리 같은 숫자를 가짐을 확인할 수 있으며 숫자가 마이너스인 경우

배열의 index로 사용할 수 없기때문에 n을 더해서 사용해주었다.

#include <iostream>

using namespace std;

bool arr[15][15];
bool check_diagonal1[40]; //오른쪽 위에서 왼쪽 밑으로 향하는 대각선
bool check_diagonal2[40]; //왼쪽 위에서 오른쪽 아래로 향하는 대각선
bool check_up_down[40]; //세로줄
int n;
int result;

int queen(int rows)
{
	if (rows == n) return 1;
	int result = 0;
	for (int i = 0; i < n ; i++)
	{
		if (!check_diagonal1[rows + i] && !check_diagonal2[rows - i + n]
			&& !check_up_down[i]) {
			check_diagonal1[rows + i] = true;
			check_diagonal2[rows - i + n] = true;
			check_up_down[i] = true;
			result += queen(rows + 1);
			check_diagonal1[rows + i] = false;
			check_diagonal2[rows - i + n] = false;
			check_up_down[i] = false;
		}
	}
	return result;
}
int main()
{
	scanf("%d", &n);

	cout << queen(0) << '\n';
}