[프로그래머스 C++] 쿼드압축 후 개수 세기

[프로그래머스 C++] 쿼드압축 후 개수 세기

 

https://school.programmers.co.kr/learn/courses/30/lessons/68936

프로그래머스

---

 

해결방안

 

쿼드트리 Quad Tree

재귀

 

---

 

코드

 

#include <vector>
using namespace std;

int zero, one; // 0 개수, 1 개수

bool Check(vector<vector<int>>& v, int ny, int nx, int size)
{
	int firstbox = v[ny][nx];

	for(int y = ny; y < ny + size; y++){
		for(int x = nx; x < nx + size; x++){
			if (v[y][x] != firstbox) return false;
		}
	}

	return true;
}

void Quad(vector<vector<int>>& v, int y, int x, int size)
{
	if (Check(v, y, x, size)) // 현재 범위의 모든 원소가 같은 값을 가지면
	{
    	// (해당 범위가 하나의 노드로 압축되므로) size의 제곱만큼 감소시킨다.
		if(v[y][x] == 0) zero -= (size*size+1);
		else if (v[y][x] == 1) one -= (size*size+1);
	}
	else // 모든 원소가 같지 않으면 범위를 4분할하여 재귀적으로 처리
    {	
		int newSize = size / 2;

		Quad(v, y, x, newSize);
		Quad(v, y + newSize, x, newSize);
		Quad(v, y, x + newSize, newSize);
		Quad(v, y + newSize, x + newSize, newSize);
	}
}

vector<int> solution(vector<vector<int>> arr) {

    int n = arr.size();
    // 모든 원소를 순회하며 0과 1의 개수를 센다.
	for(int y = 0; y < n; y++){ 
		for (int x = 0; x < n; x++) {
			if (arr[y][x] == 0) zero++;
			else one++;
		}
	}
	
	Quad(arr, 0, 0, n); // 쿼드 트리를 이용하여 개수를 세는 함수를 호출

	vector<int> answer;
	answer.push_back(zero);
	answer.push_back(one);
    
    return answer;
}

 

---

 

유사문제

 

2023.07.04 - [⭐ 코딩테스트/백준] - [백준 1992번 C/C++] 쿼드트리

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

 

---