프로그래머스(쿼드압축 후 개수 세기)-재귀

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

프로그래머스

1. 걸린 시간

20분

 

2. 트리거

쿼드 압축은 쿼드로 쪼갠 후, 모두 같은 수가 있는지 확인한다.

만약, 다 같다면, 그대로 재귀를 끝내고, 아니라면 다시 재귀에 들어간다.

import java.util.*;

class Solution {
    static int[] answer;
    public int[] solution(int[][] arr) {
        answer = new int[2];
        solve(arr);
        return answer;
    }
    
    private void solve(int[][] arr) {
        recursive(0, 0, arr.length-1, arr[0].length-1, arr);
    }
    
    private void recursive(int sy, int sx, int ey, int ex, int[][] arr) {
        if(sy == ey && sx == ex) {
            if(arr[sy][sx] == 1) answer[1]++;
            else answer[0]++;
            return;
        }
        
        boolean isAllSame = true;
        int value = arr[sy][sx];
        for(int y = sy; y <= ey; y++) {
            for(int x = sx; x <= ex; x++) {
                if(value != arr[y][x]) {
                    isAllSame = false;
                    break;
                }
            }
        }
        
        if(isAllSame) {
            answer[value]++;
        } else {
            recursive(sy, sx, (ey - sy) / 2 + sy, (ex - sx) / 2 + sx, arr);
            recursive((ey - sy) / 2 + sy + 1, sx, ey, (ex - sx) / 2 + sx, arr);
            recursive(sy, (ex - sx) / 2 + sx + 1, (ey - sy) / 2 + sy, ex, arr);
            recursive((ey - sy) / 2 + sy + 1, (ex - sx) / 2 + sx + 1, ey, ex, arr);
        }
    }
}