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

---

🔗 문제 링크

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

프로그래머스

---

728x90

반응형

👩‍💻 코드

#include <string>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

vector<int> solution(vector<vector<int>> arr) {
    int n = arr.size();
    int zero = 0;
    int one = 0;
    
    queue<tuple<int, int, int>> q;
    q.push({0, 0, n});
    
    while(!q.empty()){
        auto [x, y, size] = q.front();
        q.pop();
        
        int value = arr[x][y];
        bool same = true;
        
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                if (arr[i][j] != value) {
                    same = false;
                    break;
                }
            }
            
            if (!same) {
                break;
            }
        }
        
        if(same){
            if(value == 0){
                zero++;
            }else{
                one++;
            }
        }else{
            int newSize = size * 0.5;
            
            q.push({x, y, newSize});
            q.push({x, y + newSize, newSize});
            q.push({x + newSize, y, newSize});
            q.push({x + newSize, y + newSize, newSize});
        }
    }
    
    return {zero, one};
}

---

📝 풀이

q에 영역 검사를 시작할 좌표와 영역 크기를 저장합니다.

가장 처음 영역의 위치인 [0,0]과 크기를 push 합니다.

 

영역이 모두 동일한 값인지 확인합니다.

동일한 값이라면 값의 개수를 증가시킵니다.

 

동일한 값이 아니라면 영역을 분할하여 q에 push 합니다.

 

모든 영역이 처리될 때까지 반복한 후 {zero, one}을 return 합니다.