2020/07/02 공부 - backtracking

 방학 때 공부해서 ACM-ICPC에 나가려 팀을 모았는데, 어쩌다 팀이 터졌다. 그래서 카카오 코페나 SCPC같은 것들만 조금 해 보려 한다. 글에 한글과 영어를 많이 혼용하는데, 영어 수업을 듣다보니 이게 더 편해졌다.

 이번 학기 AI 수업을 들으면서 배웠던 backtracking을 조금 복습했다.

 backtracking은 CSP를 풀기 위해 나온 알고리즘이다. '순서'가 중요하지 않기 때문에, 내 맘대로 순서를 설정해도 되기 때문에 재귀를 이용한 DFS로 구현한다.(queue로 구현해도 되는데 재귀는 알아서 stack이 만들어지는 반면 queue는 내가 직접 만들어 줘야 해서 귀찮다. 시간복잡도에 유의미한 차이가 있는 것도 아니고) 또 brute-force와 비슷한데, 특정 조건을 만족하지 않으면 다시 back해서 탐색 시간을 줄여주는 알고리즘이다. 이 '특정 조건'을 bounding function이라 한다.

 간단하게 pseudo code를 적어봤다.

DFS(list, depth, N) {
	if (depth == N) return;
	else {
		if (bounding_function() == true)
			DFS(list, depth + 1, N)
		else
			return;
	}
}

DFS(list, 0, N)

 예제로 백준 9663번을 풀었다.

 원래는 n by n board를 만들고 queen의 위치를 표기하면서 하려 했는데, 그러면 back할 때 depth에 해당하는 row를 모두 지워 주어야 해서(귀찮아서) 각 queen은 한 줄에 1개밖에 못 들어간다는 것에 착안, n 크기의 vector를 만들고, vector[depth]에 depth번째 row에 queen이 어디 있는지를 적었다.

 앞에서 언급한 bounding function의 코드이다. 점 (x1, y1), 점 (x2, y2)에 queen이 있을 때 괜찮은지 안 괜찮은지를 검사해준다. board에서 같은 row에 있거나, 같은 column에 있거나, 대각선에 있을 때는 안 된다.

 쓰고 보니까 2개의 점을 비교하는 게 아니라, 지금까지의 queen 전부와 새로운 점을 비교하는게 좀 더 맞았던 것 같다.

bool queen_position_possible(int x1, int y1, int x2, int y2) {
	if (x1 == x2 || y1 == y2 || x1-x2 == y1-y2 || x1-x2 == y2-y1) {
		return false;
	}
	else return true;
}

  다음으로 backtrack 부분. depth가 N이면 종료하고, 아니라면 depth번째 row에 queen을 어디에 놓을지를 결정해야 한다. 코드 가독성이 조금 떨어지는 것 같긴 한데, depth가 row라고 생각하면 else문에서 각 column에서 현재까지 모든 queen에서 놓을 수 있는 조건을 만족하면 그 위치에 queen을 놓고 DFS를 한 칸 더 진행한다. backtrack에서 하는 것처럼 depth에 1을 더해주었다.

 만약 조건이 맞지 않는 경우는 더 이상 검사를 할 필요가 없기 때문에 break하고 return한다.

void DFS(vector<int> queen_list, int& ans, int depth, int N) {
	if (depth == N) {
		if (queen_list.size() == N) {
			ans++;
		}
		return;
	}
	else {
		for (int col = 0; col < N; col++) {
			bool ispossible = true;
			for (int i = 0; i < depth; i++) {
				if (queen_position_possible(i, queen_list[i], depth, col) == false) {
					ispossible = false;
					break;
				}
			}
			if (ispossible == true) {
				queen_list[depth] = col;
				DFS(queen_list, ans, depth + 1, N);
			}
		}

	}
}

​
 이제 main 부분에서 N이나 queen_list, ans 등을 선언하고 DFS에 depth를 0으로 해서 넣으면 끝.

void solve() {
	int N;
	cin >> N;
	vector<int> queen_list(N);
	int ans = 0;
	DFS(queen_list, ans, 0, N);
	cout << ans;
}

​