1780번 종이의 개수

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

1780번: 종이의 개수

---

---

<알고리즘>

  1) 입력받은 숫자를 이중 vector에 입력

  2) quadTree 응용판을 이용해 정해진 범위가 병합이 가능한지 판정

    2-1) 정해진 범위(원 사이즈 1/3크기)의 병합이 가능하면 answer에 begin input

    2-2) 병합이 불가능하면 size를 더 작게해서 재도전

  3) 9분할이 되었기에 함수 역시 각각의 범위를 가지고 9번 실행되어야함

 

 

 

 

메모리 : 69968KB     시간 : 1216ms

#include<iostream>
#include<vector>
#include<string>
using namespace std;
vector<int> answer;
void quadTreeVer2(vector<vector<int>> &p, int x, int y, int size) {
	bool isCombine = true;
	int begin = p[x][y];
	for (int j = y; j < y + size; j++) {
		for (int i = x; i < x + size; i++) {
			if (p[i][j] != begin) {
				isCombine = false;
				break;
			}
		}
		if (!isCombine) break;
	}

	if (isCombine) {
		answer.push_back(begin);
		return;;
	}

	size = (int)(size / 3);
	quadTreeVer2(p, x, y, size);
	quadTreeVer2(p, x+size, y, size);
	quadTreeVer2(p, x+2*size, y, size);

	quadTreeVer2(p, x, y+size, size);
	quadTreeVer2(p, x + size, y + size, size);
	quadTreeVer2(p, x + 2 * size, y + size, size);

	quadTreeVer2(p, x, y + 2*size, size);
	quadTreeVer2(p, x + size, y + 2 * size, size);
	quadTreeVer2(p, x + 2 * size, y + 2 * size, size);
}
int main() {
	int N = 0;
	cin >> N;

	vector<vector<int>> paper(N, vector<int>(N));
	int a = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> a;
			paper[i][j] = a;
		}
	}

	quadTreeVer2(paper, 0, 0, N);

	int minus = 0;
	int zero = 0;
	int plus = 0;
	for (int i = 0; i < answer.size(); i++) {
		if (answer[i] == -1)++minus;
		else if (answer[i] == 0) ++zero;
		else if (answer[i] == 1) ++plus;
	}
	cout << minus << "\n" << zero << "\n" << plus;
	return 0;
}