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;

}