[PS 백준 - 4.3] 1992번: 쿼드트리

문제 정보

백준 1992번 - 바로가기

• 난이도: 실버 1
• 알고리즘: 분할 정복

---

코멘트

문제의 출력 결과를 이해하는데 시간이 좀 걸렸지만, 이해하고 나니 생각보다 쉽게 풀렸다. 문제 풀이 알고리즘은 4.1 종이의 개수 문제와 거의 비슷했다.

1. 분할 정복 함수는 먼저 (starty, startx) 좌표에 있는 값을 저장하고, 이 좌표로부터 $n\times n$ 만큼 탐색을 하면서 값이 같은지 다른지를 확인한다.
2. 값이 하나라도 다르면, 괄호를 열고 $2\times 2$ 으로 영역을 쪼개서 각 영역마다 분할 정복 함수를 재귀적으로 호출한다. 4개의 영역이 다 호출되고 나면 괄호를 닫는다.
3. 값이 모두 같다면, 저장된 문자를 result에 연결한다.

---

소스 코드

#include <iostream>
#include <string>

using namespace std;

void divideConquer(int**& arr, int n, int starty, int startx, string* result) {
    int store = arr[starty][startx];
    bool flag = false;
    
    for (int i = starty; i < starty + n; i++) {
        for (int j = startx; j < startx + n; j++) {
            if (arr[i][j] != store) {
                
                // 4영역으로 가르기
                *result += "(";
                for (int a = 0; a < 2; a++) {
                    for (int b = 0; b < 2; b++) {
                        if (n > 1) {
                            divideConquer(arr, n / 2, starty + ((n / 2) * a), startx + (n / 2) * b, result);
                        }
                    }
                }
                *result += ")";

                flag = true;
                break;
            }
        }if (flag) break;
    }
    if (!flag) {
        *result += to_string(store);
    }
}

int main() {
    int n;
    cin >> n;

    int** arr = new int* [n];

    for (int i = 0; i < n; i++) {
        arr[i] = new int[n];
    }

    string result;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            char a;
            cin >> a;
            arr[i][j] = a - '0';
        }
    }

    divideConquer(arr, n, 0, 0, &result);

    cout << result;

    for (int i = 0; i < n; i++) {
        delete[] arr[i];
    }
    delete[] arr;
}