[백준 9663] N-Queen

● 문제 : 백준 9663번 : N-Queen

9663번: N-Queen

 

● 알고리즘

- 재귀함수

- 백트래킹

[백트래킹]

 

● 문제 풀이

처음에 체스판을 표현하고자 이차원 배열을 사용하였는데, 일차원 배열만으로도 문제를 해결할 수 있다는 것을 깨달았다. 입력받는 N의 크기가 최대 15이므로 크기가 15인 일차원 배열을 선언해주고, 각각의 인덱스를 퀸이 위치할 행의 번호, 그리고 그 인덱스에 들어갈 원소값을 퀸이 위치할 열의 번호로 생각하면 되는 것이다. 예를 들어, 첫 번째 줄에 두 번째 칸에 퀸이 위치한다면 arr[0]의 값은 2인 것이다. (배열의 인덱스가 0부터 시작하므로, 첫 번째 줄을 0부터 표현하였다.) 

퀸을 놓을 체스판을 설정하였다면, 체스판의 가장 윗줄부터 퀸을 놓으면서 백트래킹을 통해 조건에 맞는 경로만 탐색한다. 조건은 문제에서도 나와있지만, 퀸이 서로를 공격할 수 없는 위치 즉, 가로, 세로, 대각선 어느 줄에도 퀸이 2개 이상 존재할 수 없다는 것이다. bool position(int cnt) 이라는 함수를 만들어 조건을 검사했다. 한 줄에 하나씩만 퀸을 놓을 것이기 때문에, 가로줄은 검사해줄 필요가 따로 없고, 각 줄의 첫 번째 칸부터 차례대로 퀸을 놓아 검사를 한다. 가장 윗줄부터 현재 퀸을 놓은 줄의 윗줄까지 배열의 원소값이 같은 것이 있는지를 검사하여 세로줄을 검사한다. 대각선을 검사하는 것은 생각보다 간단하다. 배열의 원소값을 뺀 값의 절댓값이 인덱스를 뺀 값과 같은 것을 검사하면 된다. 이렇게 마지막 줄까지 퀸을 알맞게 놓았다면, 정답을 count하는 전역변수인 ans를 1 증가하여 최종적으로 몇 개의 경로가 나올 수 있는지 출력한다. 

예를 들어 N이 5라고 하면

1) arr[0]=1 -> arr={1}

맨 윗줄이므로 검사할 필요 없음 -> 재귀함수 DFS(1) 호출

2) arr[1]=1 -> arr={1,1}

3) position(1)

arr[0]==arr[1] 즉, 같은 세로줄에 있기 때문에 올바르지 않은 위치이다. -> 재귀함수가 호출되지 않음

4) arr[1]=2 -> arr={1,2}

5) position(1)

abs(arr[0]-arr[1])=1=1-0 즉, 같은 대각선에 있기 때문에 올바르지 않은 위치이다. -> 재귀함수가 호출되지 않음

6) arr[1]=3 -> arr={1,3}

7) position(1)

조건에 만족하믈 올바른 위치이다. -> 재귀함수 DFS(2) 호출

8) arr[2]=1 -> arr={1,3,1} 

9) position(2)

arr[0]==arr[2] 즉, 같은 세로줄에 있기 때문에 올바르지 않은 위치이다. -> 재귀함수가 호출되지 않음

.

.

.

이런식으로 마지막 줄까지 반복하다 보면,

arr={1,4,2,5,3}과 같이 어느 줄에도 퀸이 2개 이상 존재하지 않는 경로가 생긴다. 이럴 때마다 ans를 1 증가시킨 후, 재귀함수를 종료시킨다. 

 

● 코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <algorithm>
#include <string>
#include <cstring>
#include <climits>
#include <random>
#include <cmath>
#include <set>
#include <ctime>
using namespace std;
using ll = long long;
using ii = pair<int, int>;

int N;
int ans = 0;
vector<int>arr(15);
bool position(int cnt)
{
	for (int i = 0; i < cnt; i++)
	{
		if (arr[i] == arr[cnt] || abs(arr[i] - arr[cnt]) == cnt - i)
			return false;
	}
	return true;
}
void DFS(int cnt)
{
	if (cnt == N)
	{
		ans++;
		return;
	}

	for (int i = 0; i < N; i++)
	{
		arr[cnt] = i;
		if (position(cnt))
			DFS(cnt + 1);
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> N;
	DFS(0);
	cout << ans;
	return 0;
}