[백준/BOJ] 백준 1992번 : 쿼드트리

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

1992번: 쿼드트리

기준점(x, y)을 지정해서 지정 크기(size) 구역이 모두 같은 수라면 그 수로 압축한다. 만약 하나라도 다른 수가 존재한다면 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래로 4개의 구역으로 나눠 각각 압축을 진행한 뒤 합친다.

 

코드

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

//(x,y)의 위치를 기준으로 가로, 세로 size 크기 구역을 압축한다
string compress(vector<string> board, int size, int x, int y)
{
	string ret;
	string up_l;
	string up_r;
	string low_l;
	string low_r;
	
	int same = 1; //처음에 해당 크기 구역의 수가 모두 같다고 가정한다

	for (int i = x; i < x + size; i++)
	{
		for (int j = y; j < y + size; j++)
		{
			//하나라도 다른 수가 발견되면 반복문을 나온다
			if (board[x][y] != board[i][j])
			{
				same = 0;
				break;
			}
		}
		if (same == 0)
			break;

		//반복문 끝까지 다 같은 수 라면 그 수로 압축을 한다 
		if (i == (x + size) - 1)
			return board[x].substr(y, 1);
	}

	//4개의 구역으로 나눠 왼쪽위, 오른쪽위, 왼쪽아래, 오른쪽아래에 대해 압축을 진행한다
	up_l = compress(board, size / 2, x, y);
	up_r = compress(board, size / 2, x, y + size / 2);
	low_l = compress(board, size / 2, x + size / 2, y);
	low_r = compress(board, size / 2, x + size / 2, y + size / 2);

	ret = "(" + up_l + up_r + low_l + low_r + ")";

	return ret;
}

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

	int n;
	vector<string> board;
	string temp;
	string result;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		board.push_back(temp);
	}

	result = compress(board, n, 0, 0);

	cout << result;

	return 0;
}