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

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1992번 문제인 쿼드트리이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1992

1992번: 쿼드트리

이 문제는 문제에 주어진, 단순한 상황에서 쿼드트리(quadtree)를 구현하는 문제이다.

쿼드트리는 2차원 데이터를 압축, 저장할 수 있는 대표적인 자료구조이다. 쿼드트리는 leaf node를 제외한 각 node에서 이 node가 가리키는 2차원 데이터를 4등분한 데이터를 담고있는 node 4개를 가진다. leaf node에 저장된 값은 조각난 조각을 대표하는 값으로 볼 수 있다.

(출처: en.wikipedia.org/wiki/Quadtree)

 

이 문제에서는 0과 1로 이루어진 흑백이미지를 쿼드트리를 이용하여 압축하는 것을 구현해본다.

만약 조각에 다른 숫자가 끼어있다면, 조각을 4등분하고 각 나뉜 부분조각들에 대해서 이를 반복하면 된다.

 

각 조각에 들어있는 숫자의 총합을 이용하면 이 조각에 다른 숫자가 들어있는지 쉽게 판단할 수 있다.

n by n 조각이 1로 가득 차있다면 각 성분의 총합은 n*n일 것이고, 0으로 가득 차있다면 0일 것이기 때문이다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::string;

int screen[64][64];

void func(int n, int x, int y) {
    int num = 0;
    for (int i = x; i < x + n;i++) { // 각 조각의 모든 성분의 합
        for (int j = y;j < y + n;j++) {
            num += screen[i][j];
        }
    }
    if (num == 0) cout << 0; // 조각 성분 합이 0이면 0으로 가득 찬 것
    else if (num == n * n) cout << 1; // 조각 성분 합이 n*n이면 1으로 가득 찬 것
    else {
        n /= 2;
        cout << '(';
        func(n, x, y); // 왼쪽 위 조각
        func(n, x, y + n); // 오른쪽 위 조각
        func(n, x + n, y); // 왼쪽 아래 조각
        func(n, x + n, y + n); // 오른쪽 아래 조각
        cout << ')';
    }
}

int main()
{
    int n;
    cin >> n;
    string s;
    for (int i = 0;i < n;i++) {
        cin >> s;
        for (int j = 0;j < n;j++) {
            if (s[j] == '0') {
                screen[i][j] = 0;
            }
            else screen[i][j] = 1;
        }
    }
    func(n, 0, 0);

    return 0;
}