[Baekjoon(백준)][1992번] 쿼드트리 (C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "쿼드트리" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는 2차원 영상을 쿼드트리 방식으로 압축하는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

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

1992번: 쿼드트리

문제 개요

"쿼드트리" 문제는 2차원 영상을 쿼드트리 방식으로 압축하는 문제입니다. 이 방법은 영상을 4개의 동일한 크기 부분으로 나누고, 각 부분이 단일 색상(0 또는 1)으로 이루어져 있으면 해당 색상으로 표현하며, 그렇지 않으면 다시 4개의 부분으로 나누는 과정을 반복합니다.

해결 방법

이 문제는 재귀적인 접근을 사용하여 해결할 수 있습니다. 각 단계에서 현재 영역의 모든 픽셀이 동일한지 검사하고, 동일하지 않다면 영역을 4개로 나누어 각각에 대해 재귀적으로 같은 과정을 수행합니다.

코드 구현

#include <iostream>
#include <vector>

using namespace std;
int n; // 영상의 크기
char table[66][66]; // 영상 데이터

// 쿼드트리 압축 함수
string quard(int y, int x, int size) {
    if (size == 1) { return string(1, table[y][x]); } // 크기가 1이면 해당 셀 반환

    char temp = table[y][x];
    string ret = "";
    for (int i = y; i < y + size; i++) {
        for (int j = x; j < x + size; j++) {
            if (temp != table[i][j]) {
                // 현재 영역을 4개로 나누어 각 영역에 대해 재귀적으로 호출
                ret += '(';
                ret += quard(y, x, size / 2);
                ret += quard(y, x + size / 2, size / 2);
                ret += quard(y + size / 2, x, size / 2);
                ret += quard(y + size / 2, x + size / 2, size / 2);
                ret += ')';
                return ret;
            }
        }
    }
    return string(1, table[y][x]); // 모든 셀이 동일하면 해당 셀 반환
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; i++) {
        string temp = "";
        cin >> temp;
        for (int j = 0; j < n; j++) {
            table[i][j] = temp[j];
        }
    }
    cout << quard(0, 0, n) << "\n"; // 전체 영역에 대해 쿼드트리 압축
}

코드 설명

이 코드는 주어진 영상을 재귀적으로 쿼드트리 압축하는 방법을 구현합니다. 각 재귀 호출에서 현재 영역의 모든 픽셀이 동일한지 검사하고, 만약 동일하지 않다면 영역을 4개로 나누어 각각에 대해 다시 같은 함수를 호출합니다. 이 과정을 통해 영상을 압축한 문자열을 생성합니다.

결론

"쿼드트리" 문제는 재귀적인 접근을 사용하여 2차원 영상을 압축하는 방법을 익히는 데 유용합니다. 주어진 영역을 분할하고, 각 부분에 대해 동일한 처리를 재귀적으로 수행하는 과정을 이해하는 것이 중요합니다.