2630번 색종이 만들기

문제링크 : www.acmicpc.net/problem/2630

2630번: 색종이 만들기

---

---

<알고리즘>

  1) 주어진 수들을 vector에 넣기

  2) vector를 4분할로 나누는 쿼드트리를 이용하여 병합 가능한지 확인

     2-1) 병합이 불가능하면 pass(반복을 통해 그부분을 또 4분할 할것이기에)

     2-2) 병합이 가능하면 answer에 병합된 부분 색 입력

  3) 병합이 안되는 부분의 4분할을 반복해서 answer에 결과값 입력

  4) answer에서 숫자 1과 0을 세서 결과값 출력 

 

 

 

+) 아주 많이 참고한 블로그

chessire.tistory.com/entry/%EC%BF%BC%EB%93%9C%ED%8A%B8%EB%A6%ACQuad-tree

쿼드트리(Quad tree)

 

 

 

메모리 : 2152KB     시간 : 4ms

#include<iostream>
#include<vector>
#include<string>
using namespace std;
string answer = "";

void quadTree(vector<vector<int>> &p, int X, int Y, int size) {
	bool iscombine = true;
	int begin = p[X][Y];
	for (int y = Y; y < Y + size; y++) {
		for (int x = X; x < X + size; x++) {
			if (begin != p[x][y]) {
				iscombine = false;
				break;
			}
		}
		if (iscombine == false) break;
	}

	if (iscombine) {
		answer.append(to_string(begin));
		return;
	}

	size = int(size / 2);
	answer.append("(");
	quadTree(p, X, Y, size);
	quadTree(p, X + size, Y, size);
	quadTree(p, X, Y + size, size);
	quadTree(p, X + size, Y + size, size);
	answer.append(")");
}
int main() {
	int N = 0;
	cin >> N;
	
	vector<vector<int>> paper(N + 1, vector<int>(N + 1));
	int input = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> input;
			paper[i][j] = input;
		}
	}

	quadTree(paper, 0, 0, N);

	int white = 0;
	int blue = 0;
	for (unsigned int i = 0; i < answer.size(); i++) {
		if (answer[i] == '(' || answer[i] == ')')
			continue;
		else if (answer[i] == '1') ++blue;
		else if (answer[i] == '0')++white;
	}
	cout << white << "\n" << blue;
	return 0;
}