2020/07/04 공부 - backtracking
오늘은 저번에 이어 backtrack의 다른 예제를 풀었다. 백준 2580번 스도쿠이다. 내가 알고 있는 CSP와 굉장히 유사한 문제이기 때문에 backtrack으로 푸는 것이 좋다. 숫자를 채워 넣을 때 lookahead 등의 heuristics를 쓸 수도 있지만 귀찮아서 순서대로 채워 넣었다.
먼저 backtrack의 pseudo code는 다음과 같았다. 이 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)
스도쿠에서 boundnig function은 다음과 같이, 가로줄/세로줄/3by3 그룹에서 모든 숫자를 2번 이상 사용했으면 안 된다.(문제에서 주어져 있으므로 세부 설명은 생략) C++을 오랜만에 만져봐서 배열을 초기화하는 데 자꾸 컴파일 에러가 걸려서 애먹었다. 코드가 좀 난잡하긴 하지만 하나하나 확실하게 하는 것에 초점을 두었다.
// 어떤 새로운 row, col에 숫자 n을 집어넣었을 때 스도쿠 규칙을 안 깨는지 검사해주는 함수. 깨면 false, 안깨면 true return.
bool sudoku_possible(vector<vector<int>>& board, int row, int col, int n) {
int one_to_nine_arr[10] = {};
// 세로줄 검사
for (int i = 1; i <= 9; i++) {
one_to_nine_arr[board[i-1][col]]++;
}
one_to_nine_arr[n]++;
for (int i = 1; i <= 9; i++) {
if (one_to_nine_arr[i] >= 2) return false;
}
// 가로줄 검사
for (int i = 1; i <= 9; i++) one_to_nine_arr[i] = 0;
for (int i = 1; i <= 9; i++) {
one_to_nine_arr[board[row][i-1]]++;
}
one_to_nine_arr[n]++;
for (int i = 1; i <= 9; i++) {
if (one_to_nine_arr[i] >= 2) return false;
}
// 3 by 3 그룹 검사
for (int i = 1; i <= 9; i++) one_to_nine_arr[i] = 0;
int row_group = row / 3;
int col_group = col / 3;
for (int i = 3*row_group; i < 3 * row_group + 3; i++) {
for (int j = 3 * col_group; j < 3 * col_group + 3; j++) {
one_to_nine_arr[board[i][j]]++;
}
}
one_to_nine_arr[n]++;
for (int i = 1; i <= 9; i++) {
if (one_to_nine_arr[i] >= 2) return false;
}
return true;
}
다음으로 DFS 부분이다. 기존에 비어 있던 칸들(0으로 입력되어 있는 부분)을 blank라는 pair vector로 입력받았고 blank의 size가 DFS에서 목표로 하는 depth가 될 것이다. 이 값을 blank_num으로 했고 각 depth에서 blank[depth]를 탐색하게 만들었다.
DFS를 void로 선언했기 때문에 complete라는 새로운 변수를 하나 넣어서 이게 true이면 종료 조건을 달성하게 만들었다.
bounding funtion 부분은 blank[depth]에 1부터 9까지 수를 넣었을 때, 만족하면 다음 DFS를 진행하고, 만약 이 DFS 결과 complete가 참이라면 바로 return하게 만들었다. 만약 불가능하다면 다음 수를 탐색하게 만들었고, 이 때 1부터 9까지 모든 수가 불가능하다면 채워넣은 칸을 0으로 다시 초기화한 뒤 return했다.
void DFS(vector<vector<int>>& board, vector<pair<int, int>>& blank, int depth, int blank_num, bool& complete) {
if (depth == blank_num || complete == true) {
complete = true;
return;
}
else {
bool ispossible = false;
for (int i = 1; i <= 9; i++) {
if (sudoku_possible(board, blank[depth].first, blank[depth].second, i)) {
board[blank[depth].first][blank[depth].second] = i;
DFS(board, blank, depth + 1, blank_num, complete);
if (complete == true) return;
continue;
}
}
board[blank[depth].first][blank[depth].second] = 0;
return;
}
}
전체적인 코드의 구조는 pseudo code와 동일하게 만들었다. 아래 코드는 입/출력 부분이다.
void solve() {
int blank_num = 0; // 채워야 하는 것들 개수
vector<vector<int>> board(9, vector<int>(9)); // 스도쿠 판
vector<pair<int, int>> blank; // 빈 칸 list
bool complete = false;
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
int input;
cin >> input;
board[row][col] = input;
if (input == 0) {
blank.push_back({ row, col });
blank_num++;
}
}
}
DFS(board, blank, 0, blank_num, complete);
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
cout << board[row][col]<<' ';
}
cout << '\n';
}
}
다음, 14888번을 풀었다. 이 문제는 search 과정에서 bounding function을 사용하지 않고 leaf node에서 bounding function을 사용하기 때문에 backtrack이라기보다는 재귀를 이용한 DFS라는 주제가 조금 더 맞는 것 같은데, 일단 backtrack 주제에 포함되어 있어서 여기서 풀었다.
연산자 4종류를 나열할 수 있는 수는, (N-1)! / [(+)!(-)!(*)!(/)!] 일 것이다. 여기서 N = 12이므로 11!은 약 300백만이고, 컴퓨터가 1초에 약 10억개의 연산을 할 수 있으니 연산량은 충분하므로 완전 탐색으로 진행해도 된다.
고등학교 과정에서 배우는 수의 나열을 위해 DFS를 진행한다. 이 문제는 brute-force에 좀 더 가깝기 때문에 backtrack에서 사용하기 위한 bounding function은 없다.
DFS는 다음과 같다. 이렇게 진행하면 각 연산자의 숫자가 0이 될 때까지 모든 경우의 수를 알아서 계산해 준다. 앞과 같이 depth와 최대 depth의 크기를 받아서 depth가 N-1과 같아지면 그만하고 return. 아니라면 탐색을 계속 진행한다.
void DFS(vector<int>& arr, int num_plus, int num_minus, int num_mul, int num_div, int depth, int N, int cal_result, int& max_num, int& min_num) {
if (depth == N-1) {
max_num = max(cal_result, max_num);
min_num = min(cal_result, min_num);
}
else {
if (num_plus > 0) {
DFS(arr, num_plus - 1, num_minus, num_mul, num_div, depth + 1, N, cal_result + arr[depth + 1], max_num, min_num);
}
if (num_minus > 0) {
DFS(arr, num_plus, num_minus - 1, num_mul, num_div, depth + 1, N, cal_result - arr[depth + 1], max_num, min_num);
}
if (num_mul > 0) {
DFS(arr, num_plus, num_minus, num_mul - 1, num_div, depth + 1, N, cal_result * arr[depth + 1], max_num, min_num);
}
if (num_div > 0) {
DFS(arr, num_plus, num_minus, num_mul, num_div - 1, depth + 1, N, cal_result / arr[depth + 1], max_num, min_num);
}
}
}
입력부는 다음과 같다.
void solve() {
int N;
cin >> N;
vector<int> arr(N);
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
vector<int> simple_operator(4);
for (int i = 0; i < 4; i++) {
cin >> simple_operator[i];
}
int max_num = -1000000001;
int min_num = +1000000001;
DFS(arr, simple_operator[0], simple_operator[1], simple_operator[2], simple_operator[3], 0, arr.size(), arr[0], max_num, min_num);
cout << max_num << '\n' << min_num;
}