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

 

쿼드트리

 

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

1992번: 쿼드트리

---

 

해결전략

 

재귀

 

 

---

 

코드

 

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

int n;
string input;
vector<vector<int>> v;

bool Check(int y, int x, int size)
{
    int firstValue = v[y][x];

    for (int i = y; i < y + size; i++) {
        for (int j = x; j < x + size; j++)
        {
            if (v[i][j] != firstValue) return false;
        }
    }

	return true;
}

void Quad(int y, int x, int size)
{
	if (Check(y, x, size))
		cout << v[y][x];

	else 
	{
		int newSize = size / 2;

		cout << "(";

        Quad(y, x, newSize);
        Quad(y, x + newSize, newSize);
        Quad(y + newSize, x, newSize);
        Quad(y + newSize, x + newSize, newSize);

        cout << ")";
	}
}

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

    cin >> n;
    v.resize(n, vector<int>(n));

    for (int i = 0; i < n; i++) {
        cin >> input;

        for (int j = 0; j < n; j++) {
            v[i][j] = input[j] - '0';
        }
    }

    Quad(0, 0, n);

    return 0;
}

 

---

 

해설

 

이 코드는 그림 데이터를 이용하여 사분면 트리를 구축하는 문제의 해답입니다. 주요 구성요소와 로직에 대해 설명하겠습니다.

1. n은 그림의 크기를 저장하는 변수입니다. 이 값은 입력을 통해 주어집니다.
2. input은 입력받을 한 줄의 문자열입니다.
3. v는 2차원 벡터로, 그림 데이터가 저장됩니다.
4. bool Check(int y, int x, int size) 함수는 주어진 y, x 좌표를 시작점으로 하는 크기(size x size) 구간에 동일한 값이 모두 존재하는지 확인하며, 그 결과를 반환합니다.
5. void Quad(int y, int x, int size) 함수는 재귀적으로 크기를 줄여가며 사분면을 확인하고 압축 과정을 진행합니다. 만약 주어진 구간에 동일한 값만 존재한다면 그 값을 출력하고, 아니라면 그 구간을 사분면으로 나누어 다시 확인합니다.
6. main 함수에서는 그림 데이터를 입력 받고, Quad 함수를 호출하여 압축 결과를 출력합니다.

이 코드는 주어진 그림 데이터를 이용하여 사분면 트리를 구축하고, 압축된 결과를 출력합니다.

 

 

 

 

---