GitHubSeob

C++ / 백준 / 1992 / 쿼드트리 본문

Baekjoon/Silver

C++ / 백준 / 1992 / 쿼드트리

GitHubSeob 2021. 8. 25.

문제

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

 

1992번: 쿼드트리

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또

www.acmicpc.net

문제풀이

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

1780문제와 거의 유사하게 풀었다.

1780번과 다른 점은 괄호의 유무와 칸을 분할할때 4등분을 하는점, 개수를 세는 것이 아닌 값을 출력하는 점 이다.

 

띄어쓰기 없이 입력받으므로 string으로 입력받고 끝자리의 0을 빼고 입력받는다.

0, 0부터 탐색을 시작한다.

			if (y != prev_y && (max_value != min_value || max_value != prev_max || min_value != prev_min)) {
				cout << "(";
				Divide(prev_y, prev_x, size / 2);
				Divide(prev_y, prev_x + size / 2, size / 2);
				Divide(prev_y + size / 2, prev_x, size / 2);
				Divide(prev_y + size / 2, prev_x + size / 2, size / 2);
				cout << ")";
				break;
			}

처음에는 이전 최솟값, 이전 최댓값이 없으니 그 때를 제외하고 반복을 하면서 값이 서로 다르면 4등분을 한다.

 

		if (y == prev_y + size)
			cout << quad[y - 1][x];

조건에 해당하지 않아 모든 반복문을 돌면 탐색한 부분의 값이 모두 같으므로 해당 값을 출력한다.

4등분 하는것도 중요하지만, 괄호를 쓰는 위치도 중요하다.

나누기 전에 (, 나누고 난후에 )만 써주면 된다.

 

코드

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

vector<vector<int>>quad;

void Divide(int y, int x, int size) {
	if (size == 1)
		cout << quad[y][x];
	else {
		int prev_y = y;
		int prev_x = x;
		int max_value = 0;
		int min_value = 0;
		for (y; y < prev_y + size; ++y) {
			int prev_min = min_value;
			int prev_max = max_value;
			max_value = *max_element(quad[y].begin() + x, quad[y].begin() + x + size);
			min_value = *min_element(quad[y].begin() + x, quad[y].begin() + x + size);

			if (y != prev_y && (max_value != min_value || max_value != prev_max || min_value != prev_min)) {
				cout << "(";
				Divide(prev_y, prev_x, size / 2);
				Divide(prev_y, prev_x + size / 2, size / 2);
				Divide(prev_y + size / 2, prev_x, size / 2);
				Divide(prev_y + size / 2, prev_x + size / 2, size / 2);
				cout << ")";
				break;
			}
		}
		if (y == prev_y + size)
			cout << quad[y - 1][x];
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N;
	cin >> N;
	quad = vector<vector<int>>(N, vector<int>(N, 0));
	int y = 0, x = 0;

	for (y = 0; y < N; ++y) {
		string num = "";
		cin >> num;
		for (x = 0; x < N; ++x)
			quad[y][x] = num[x] - '0';
	}
	Divide(0, 0, N);
}