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

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

1992번: 쿼드트리

문제

풀이

이 문제는... 처음에 이해하는게 힘들었다.

풀이 하자면 문제에서 요구하는 방법은 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 즉 Z 순서로 

숫자를 비교하고 탐색하는 것이다.

위 이미지 같은 경우 (01(1101)(0011)이 되는것 이다.

 

그렇다면, N은 항상 2의 제곱수로 주어지니,

첫번째로 영상의 모든 수가 동일한지 확인하고, 동일하지 않다면

모든 비디오 영상을 4등분하여 왼쪽위, 오른쪽위, 왼쪽아래, 오른쪽아래의 숫자가 동일한지 확인한다.

이 작업을 반복하며, 분할정복 방법으로 문제를 해결해 나가면 된다.

 

우선 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 식을 세운 후, 차근차근 문제를 해결해 나가면 된다.

문제 난이도 보다 처음에 문제 이해가 더 힘들었던 문제...

 

Code ( C++ )

#include<iostream>
using namespace std;

string s;
int N;
int video[64][64];

void solve(int y, int x, int size)
{
	for (int i = y; i < y + size; i++)
		for (int j = x; j < x + size; j++)
		{
			if (video[i][j] != video[y][x])
			{
				cout << "(";
				solve(y, x, size / 2);
				solve(y, x + size / 2, size / 2);
				solve(y + size / 2, x, size / 2);
				solve(y + size / 2, x + size / 2, size / 2);
				cout << ")";
				return;
			}
		}
	cout << video[y][x];
}

int main()
{
	// 입력은 문자열로 입력하기 때문에 
	// 아스키 코드를 사용해 문자를 숫자로 변경해주어서 video 배열에 저장한다.
	
	cin >> N;
	for (int y = 0; y < N; y++)
	{
		cin >> s;
		for (int x = 0; x < N; x++)
			video[y][x] = s[x] - '0';
	}
	solve(0, 0, N);

}