[BOJ 9663] N-Queen +)백트래킹

 

DFS는 현재 지점에서 방문할 곳이 있으면 재귀 호출을 통해 계속해서 이동한다. (무한히 깊은곳을 찾을때 좋음!)

하지만 목표지점이 있지 않은 경로로 빠져서 비효율적일수도 있다.

-> 가능성이 없는애들을 가지치기 해버리는것,

즉 비효율적인 경로를 차단하고 목표지점에 갈수있는 가능성이 있는 루트를 검사하는 방법이 백트래킹 알고리즘이다.

 

백트래킹의 가장 기본문제

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

#include <iostream>
using namespace std;

int n; int res = 0;
int col[15];

bool pos(int k) {
	for (int i = 0; i < k; i++) {
		if (col[i] == col[k])
			return false;
		if (abs(col[k] - col[i]) == k - i)
			return false;
	}
	return true;
}

void dfs(int k) {
	if (k == n) {
		res++; return;
	}
	for (int i = 0; i < n; i++) {
		col[k] = i;
		if (pos(k))
			dfs(k + 1);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	dfs(0);
	cout << res;
}

---

N-Queen 문제 설명

 

빨간퀸을 (1,1)에 위치시키면 가능한 애들은 3,4번째에 있던 검은 퀸들이다.

dfs로 수행했을땐 (2,1)(2,2) 도 검사했을 것이라 확실히 속도가 줄어든다.

 

 

1. 다시 말하면 (1,1) 에서 시작하여 일단 (2,1) 노드로 간다.

2. (2,1)노드는 (1,1)과 같은 열에 위치해 있기때문에 가능성 없어서 다시 (1,1)로 백트래킹

3. (2,2)노드 이동하지만 대각선 위치! 다시 (1,1)로 백트래킹

4. (2,3) 노드 이동, 이동반경에 포함되지 않아서 다음 퀸 위치 찾는다.

 

-> 이렇게 계속해서 가지치기 하고 돌아가고 가지치기! 돌아가고!

나는 처음에 계속 디버깅하면서 하느라 4*4로 빠짝 이해했다......