[Baekjoon] 1992 - 쿼드트리

문제

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

1992번: 쿼드트리

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

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

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다.  N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

---

풀이

이차원 배열에서 중간점을 찾아 가면서 만약 최소 단위에 다다르면 따로 처리를 해 주고, 각각의 반환받은 결과를 조합해 다시 결과를 반환하는 방식이다.

큰 문제를 작은 문제로 쪼개어 해결하는 분할 정복법 유형이다.

배열에서 이진 트리를 탐색할 때 인덱스를 *2 해주면 왼쪽 자식 노드로 가는 것과 비슷한 방법으로 더 하위 배열로 접근하면서 최소 단위인지 확인한다.

 

까다로웠던 점

n = 0일때 dfs()에서 예외처리를 해줘야 했다. (n > 1인 경우는 n == 1까지만 재귀함수가 들어가기 때문. n = 1로 처음부터 입력을 받으면 함수 내에선 n = 0으로 들어오기 때문에.)

 

반환받은 결과가 모두 같을 때 뿐만 아니라, 그 결과가 0 또는 1인 경우에만 "압축"을 해줘야 한다.

만약 그 결과가 "0"이나 "1"이 아니라면, 압축을 하면 안된다.

 

더 배울 점

반례 데이터를 생각해볼때 조금 더 생각을 해보고 반례를 검색해보자.

 

소스코드

// Baekjoon No. 1992 - 쿼드트리, 220921 solved
// Time Complexity O(n^2)
// #Quad Tree (Binary Tree)

#include <iostream>
#include <vector>
#include <string>
using namespace std;

string dfs(vector<string>& map, int n, int row, int col);
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    int i, j;
    cin >> n;
    vector<string> map(n);
    for (i = 0; i < n; i++) {
        cin >> map[i];
    }

    // solving
    cout << dfs(map, n / 2, n / 2, n / 2);
    
    return 0;
}
string dfs(vector<string>& map, int n, int row, int col) {
    if (n == 0) {
        return "0";
    }else if (n == 1) {
        string s1(1, map[row - 1][col - 1]);
        string s2(1, map[row - 1][col]);
        string s3(1, map[row][col - 1]);
        string s4(1, map[row][col]);
        if (s1 == s2 && s2 == s3 && s3 == s4 && (s1 == "0" || s1 == "1"))
            return s1;
        else
            return "(" + s1 + s2 + s3 + s4 + ")";
    }
    else {
        string s1 = dfs(map, n / 2, row - n / 2, col - n / 2);
        string s2 = dfs(map, n / 2, row - n / 2, col + n / 2);
        string s3 = dfs(map, n / 2, row + n / 2, col - n / 2);
        string s4 = dfs(map, n / 2, row + n / 2, col + n / 2);
        if (s1 == s2 && s2 == s3 && s3 == s4 && (s1 == "0" || s1 == "1"))
            return s1;
        else
            return "(" + s1 + s2 + s3 + s4 + ")";
    }
}