[BOJ/백준 1992][C++] 쿼드트리

문제

https://www.acmicpc.net/problem/1992

백준 1992

 

문제 내용

배열을 입력받아 규칙대로 압축을 진행하면 된다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

 

문제 풀이

재귀를 사용하여 문제를 해결할 수 있다.

먼저 범위에 해당되는 부분이 다 같은 수로 채워져 있는지를 체크하고, 그렇지 않으면 4등분으로 분할하여 각각에 대해 같은 과정을 거친다.

만약 다 같은 수로 채워져 있으면 결과에 압축 내용을 추가하면 된다.

 

이 문제에서 4등분을 할 때는 반드시 탐색 순서에 맞춰서 해야한다.

또한 4등분 전후로 괄호를 추가해야 한다.

 

코드

#include <iostream>

using namespace std;

int arr[64][64];
int n;
string result = "";

bool check(int r, int c, int len) {
    int num = arr[r][c];
    for (int i = 0; i < len; i++)
        for (int j = 0; j < len; j++)
            if (arr[i + r][j + c] != num)
                return false;

    return true;
}

void checkAndDivide(int r, int c, int len) {
    if (len == 1 || check(r, c, len)) {
        result += to_string(arr[r][c]);
        return;
    }

    // 4분면으로 분할
    result += "(";
    len /= 2;
    checkAndDivide(r, c, len);             // 왼쪽 위
    checkAndDivide(r, c + len, len);       // 오른쪽 위
    checkAndDivide(r + len, c, len);       // 왼쪽 아래
    checkAndDivide(r + len, c + len, len); // 오른쪽 아래
    result += ")";
}

int main() {
    cin >> n;

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

    checkAndDivide(0, 0, n);
    cout << result;
}

 

문제 코드 설명

입력이 공백 없이 주어지기 때문에 string으로 입력받아 한글자씩 분리해야 한다.