[알고리즘] 백준 1992 쿼드트리

 

백준 1992

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

1992번: 쿼드트리

 

풀이 전 내 생각

나는 트리라고 하길래 처음엔 트리 자료구조를 써서 푸는 건줄 알았다.. 

각설하고 문제를 보면 이미지를 압축하는데 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 진행한다고 한다.

대신 0과 1이 섞여있으면 전체를 한번 더 나눈 후 반복하여 이미지를 압축한다. 뭔가 계속 나누는걸 보니 재귀를 사용한다는 것을 예측할 수 있다. 그러면 네모 모양의 4개의 압축 이미지를 반복되는 규칙에 의해 압축하면 되는 문제로 보인다.

그럼 각각의 이미지에 0과 1이 섞여있는지 아닌지 알아야 하니 이미지 크기 만큼 배열을 순회해야 한다. -> 2중 for문

대신 0과 1이 섞여있으면 다시 나눠서 이미지 압축 순서를 반복한다. -> if(0과 1이 섞여있으면?) 재귀

그럼 2중 for문 안에 재귀를 넣어 놓으면 해결할 수 있는 문제라고 추측할 수 있다. 그럼 재귀를 한번 돌 때 마다 사이즈는 반씩 줄어들 것이고 각 이미지 순서마다 배열 순회의 시작점과 끝점을 계산해서 넣어주면 될 것이다.

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;
string screen[64];

void Recur(int size, int x, int y)
{
	char fVal = screen[y][x];

	for (int i = y; i < y + size; i++)
	{
		for (int j = x; j < x + size; j++)
		{
			if (fVal != screen[i][j])
			{
				cout << '(';
				Recur(size / 2, x, y);
				Recur(size / 2, x + size / 2, y);
				Recur(size / 2, x, y + size / 2);
				Recur(size / 2, x + size / 2, y + size / 2);
				cout << ')';
				return;
			}
		}
	}
	cout << fVal;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int N = 0;
	
	cin >> N;
	for (int i = 0; i < N; i++) 
	{
		cin >> screen[i];
	}

	Recur(N, 0, 0);
}