백준 9663 N-Queen

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

 

서론

백트래킹을 이해하기 위해 풀어본 문제

퀸이 위치할 수 있는 조건을 만드는것, 퀸이 놓일때 이전에 놓인 퀸들을 모두 고려해야하는것, 재귀를 시작할 위치를 지정하는것을 생각하는데 꽤나 오래걸렸다.

걸린시간대비 결과물이 짧은 코드이지만 간결하게 나온것 같아서 만족한다.

 

---

아이디어 & 풀이과정

DFS

조건을 만족하려면 각 행에는 하나의 퀸만 둘 수 있다.

DFS를 이용하여 1행부터 n행까지 각 행마다 하나씩 퀸을 두면서 가능한 모든 경우의 수를 탐색한다.

 

set A

1행 1열에 퀸을 하나 놓고 행을 증가시켜 모든 열을 탐색한다.

2행 1열에 퀸을 놓아보지만 조건을 만족하지 않으므로 리턴한다.

2행 2열도 안되므로 리턴

2행 3열은 가능하므로 퀸을 놓고 행을 증가시키고 모든 열을 탐색한다.

3행은 모든 열에서 퀸을 놓을 수 없다. 2행 3열에 퀸을 놓으면 n개를 놓을 수 없으므로 리턴한다.

 

위 set A는 1행 1열을 시작점으로 잡았기 때문에 위와 같은 절차를 1행 2열, 1행 3열 ...1행 n열까지 해줘야 한다.

모든 행에 퀸이 하나씩 들어가는 경우가 나오면 출력값을+1 해주면 된다.

 

조건

3번째 퀸이 놓일때 1행 퀸도 고려해야하지만 2행 퀸도 고려해야 한다.

1행의 퀸 좌표는 arr[1], 2행의 퀸 좌표는 arr[2]와 같은 식으로 행을 하나씩 증가시킬때마다 좌표를 배열에다 넣고

4번째 퀸이 놓일때는 arr[1] ~ arr[3]까지의 모든 좌표를 확인하여 조건을 판단해야한다.

 

조건 : 

현재 퀸과 이전퀸 좌표의 행이 같으면 리턴

현재 퀸과 이전퀸 좌표의 열이 같으면 리턴

현재 퀸 좌표와 이전퀸 좌표의 행 차이와 열 차이가 같으면 리턴

  

---

구현

//c++

#include <iostream>
#include <vector>

using namespace std;

int n;
int result;
pair<int, int> check[15];

void dfs(int row, int column) {
	for (int i = 0; i < row; i++) {
		if (check[i].first == row || check[i].second == column || abs(check[i].first - row) == abs(check[i].second - column)) {
			return;
		}
	}
	//cout << row << " " << column << endl;

	if (row >= n-1) {
		result++;
		return;
	}

	for (int i = 0; i < n; i++) { 
		check[row] = { row, column };
		dfs(row + 1, i); 
	}
	return;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) dfs(0, i);
	cout << result;
}