쿼드압축 후 개수 세기 (백트래킹)

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

프로그래머스

 

 

 

문제 풀이

 주어진 배열을 재귀 함수를 이용한 백트래킹으로 계속 사분면으로 나누면서 사분면 내 모든 숫자가 같은지 판단하면 된다. 사실 아직 문제의 해결법으로 백트래킹이 잘 떠오르지 않아서 힌트를 좀 보고 나서야 해결법을 생각할 수 있었다.

 

 

작성한 코드 (정답 코드)

class Solution {
    
    public int[] solution(int[][] arr) {
        int[] answer = {0,0};
        
        backTracking(arr, 0, 0, arr.length, answer);
        
        return answer;
    }
    
    public void backTracking(int[][] arr, int startX, int startY, int size, int[] answer) {

        int firstValue = arr[startX][startY];

        if (isSame(arr, startX, startY, size)) {
            answer[firstValue]++;
            return;
        }

        if (size < 2) return;

        // 1사분면
        backTracking(arr, startX + (size/2), startY, size/2, answer);

        // 2사분면
        backTracking(arr, startX, startY, size/2, answer);

        // 3사분면
        backTracking(arr, startX, startY + (size/2), size/2, answer);

        // 4사분면
        backTracking(arr, startX+ (size/2), startY+ (size/2), size/2, answer);

    }
    
    public boolean isSame(int[][] arr, int startX, int startY, int size) {

        int firstValue = arr[startX][startY];

        for (int i = startX; i < startX + size; i++) {
            for (int j = startY; j < startY + size; j++) {

                if (arr[i][j] != firstValue) return false;

            }
        }

        return true;
    }        
}