분할 정복(Divide and Conquer)
개발/알고리즘

분할 정복(Divide and Conquer)

분할 정복(Divide and Conquer)은 이름에서도 알 수 있듯이 어떤 문제를 분할하고 분할된 부분 문제(Subproblem)을 각각 정복하여 합쳐서 원래 문제를 해결해 내는 알고리즘 설계 방법이다. 분할하다 기저 사례(Base case)가 나오면 기저 사례는 더 이상의 분할 없이 계산할 수 있다.

 

이 문제를 예시로 들겠다. 기저 사례는 종이의 내부 색이 모두 같거나 종이가 1x1 사이즈일 때다. 그러면 위 그림을 기저 사례까지 분할하는 과정을 짚어보겠다. 우선 각 단계마다 기저 사례인지 확인해야 한다.

 

첫 번째 단계에서는 1x1 사이즈도 아니고 내부 색이 모두 같지도 않으므로 바로 해결할 수 없다. 따라서 분할을 해야 한다. 분할을 어떻게 하면 좋을까? 종이의 사이즈가 항상 $2^n \times 2^n$인 것을 이용하여 항상 가로 2등분, 세로 2등분(전체를 4등분)하면 1x1까지 문제 없이 도달할 수 있다.

 

처음 종이 분할하기

 

처음 종이를 4분할하면 위와 같이 된다. 이 네 영역을 각각 $N_1, N_2, N_3, N_4$라고 하겠다. 4분할 하는 것을 어떻게 할 지 잘 떠오르지 않을 수도 있는데, 왼쪽 상단의 좌표와 변의 길이를 이용해 재귀 호출을 이용할 수 있다.

void solve(int x, int y, int d) {
    // 중략

    // 재귀 호출
    solve(x, y, d/2); // 왼쪽 상단
    solve(x + d/2, y, d/2); // 오른쪽 상단
    solve(x, y + d/2, d/2); // 왼쪽 하단
    solve(x + d/2, y + d/2, d/2); // 오른쪽 하단
}

 

 $N_1$ 분할하기

 

 

분할된 $N_1$의 내부 색이 모두 같지 않으므로 다시 한 번 위와 같이 $N_{1_1}, N_{1_2},N_{1_3},N_{1_4}$로 분할해야 한다. $N_{1_1}, N_{1_2},N_{1_3},N_{1_4}$의 내부 색은 모두 같으므로 이제 각 색깔별로 카운트를 해 주면 된다.

 

$N_2$ 분할하기

 

이제 $N_2$로 간다. 역시 내부 색이 모두 같지 않으므로 위와 같이 $N_{2_1}, N_{2_2},N_{2_3},N_{2_4}$로 분할한다. $N_{2_1}, N_{2_2},N_{2_3},N_{2_4}$의 내부 색은 모두 같으므로 역시 각 색깔별로 카운트 해 주면 된다.

 

$N_3$ 분할하기

 

이제 $N_3$으로 간다. 내부 색이 모두 같지 않으므로 위처럼 $N_{3_1}, N_{3_2},N_{3_3},N_{3_4}$로 4분할을 하게 된다.

 

$N_{3_1}$은 내부 색이 모두 같지 않다. 따라서 한번 더 4분할을 해주면 이제는 1x1 사이즈가 되고, 기저 사례이기 때문에 색깔별로 카운트 할 수 있다. $N_{3_2}, N_{3_3}, N_{3_4}$는 내부 색이 모두 같으므로 카운트하면 된다.

 

$N_4$로 간다. $N_4$는 내부 색이 모두 같으므로 그냥 카운트 할 수 있다. 이제 모든 탐색 과정이 끝났으므로 지금까지 카운트한 각 색깔별 종이의 개수가 답이 된다. 지금까지 분할한 과정을 그림으로 나타내면 다음과 같다.

 

 

이 과정을 코드로 구현하면 다음과 같다. 분할 정복을 이용하여 문제를 해결할 때에는 재귀 함수를 이용하는 경우가 많다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int board[129][129];
int B, W;

void solve(int x, int y, int d) {
    int start = board[x][y]; // 맨 좌측 상단

    // 크기가 1 x 1이면 기저 사례이므로 카운트
    if (d == 1) { 
        if (start == 0) W++;
        else B++;
        return;
    }

    // 내부 색이 모두 같은지 확인
    bool isInsideSame = 1;
    for (int i = 0; i < d; i++) {
        for (int j = 0; j < d; j++) {
            if (board[x+i][y+j] != start) {
                isInsideSame = 0;
                i = d, j = d; continue; // break
            }
        }
    }

    // 내부 색이 모두 같다면 기저 사례이므로 카운트
    if (isInsideSame) {
        if (start == 0) W++;
        else B++;
        return;
    }

    // 기저 사례가 아니면 4분할
    int l = d / 2;
    solve(x, y, l);
    solve(x+l, y, l);
    solve(x, y+l, l);
    solve(x+l, y+l, l);
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);

    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) cin >> board[i][j];
    }

    solve(0, 0, n);
    cout << W << '\n' << B;
}

 

이러한 방식으로 문제를 분할하여 해결하는 문제 해결 기법이 분할 정복이다. 분할 정복 기법은 그 자체로 많이 사용되지는 않지만, 다른 문제 해결 과정의 기초가 되는 경우가 많기 때문에 굉장히 중요한 문제 해결 기법이라고 할 수 있다.

    티스토리툴바