[programmers][X] 쿼드압축 후 개수 세기

26 Jun 2023 in Algorithm on Algorithm

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

import java.util.*;

class Solution {
    public int[] solution(int[][] arr) {
        int[] answer = new int[2];

        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0,0,arr.length,arr[0].length});

        while(!q.isEmpty()){
            int len = q.size();
            for(int i = 0; i < len ; i++){
                int[] temp = q.poll();

                boolean isSame = true;
                int val = arr[temp[0]][temp[1]];
                for(int x = temp[0] ; x < temp[2] ; x++){
                    for(int y = temp[1] ; y < temp[3] ; y++){
                        if(val != arr[x][y]){
                            isSame = false;

                            int startX = temp[0];
                            int startY = temp[1];
                            int lastX = temp[2];
                            int lastY = temp[3];

                            int midX = (startX + lastX) / 2;
                            int midY = (startY + lastY) / 2;

                            q.offer(new int[]{startX, startY, midX, midY});
                            q.offer(new int[]{startX, midY, midX, lastY});
                            q.offer(new int[]{midX, startY, lastX, midY});
                            q.offer(new int[]{midX, midY, lastX, lastY});

                            break;
                        }
                    }
                    if(!isSame) break;
                }
                if(isSame) answer[val]++;
            }
        }

        return answer;
    }
}