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

코딩테스트 연습 - 쿼드압축 후 개수 세기 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 쿼드압축 후 개수 세기

어떻게 생각하고 문제를 풀었는가?

압축한 영역이 모두 같은 숫자를 가지고 있는지 확인하기 위해서는 내부의 영역이 나타내는 숫자를 확인하여야 합니다.

가장 작은 영역단위(1x1크기)부터 숫자를 파악하고, 다음 크기의 영역단위에서 4개의 영역이 같은 숫자라면 영역을 하나의 숫자로 압축시킴으로서 문제를 해결할 수 있다고 생각하였습니다.

 

코드

class Solution {
    private int[] answer = {0,0};
    private int[][] tree;
    public int[] solution(int[][] arr) {
        tree = arr;
        quadCount(0,0,arr.length);        

        return answer;
    }
    private int quadCount(int x, int y, int size){
        if(size==1){
            answer[tree[x][y]]++; //최소 단위에서 결과값을++
            return tree[x][y];
        }        
        //4개의 구역으로 나눈다.
        int nsize = size/2;
        int lt = quadCount(x,y,nsize);
        int rt = quadCount(x+nsize,y,nsize);
        int lb = quadCount(x,y+nsize,nsize);
        int rb = quadCount(x+nsize,y+nsize,nsize);
        //4개의 구역이 공통되면 압축, 이미 압축되지 않은 구역이 있다면 압축하지 않는다.
        if(lt!=-1 && lt==rt && lt==lb && lt==rb){   
            answer[lt]-=3;
            return lt;  
        }else return -1;//서로 다른 값을 가지면 압축하지 않는다.
    }
} 

테스트를 통과하는 코드입니다.

재귀함수를 사용한 DFS로서 코드를 작성하였으며 4개의 영역이 같다면 영역이 나타내는 숫자를 반환하고 다르다면 -1을 반환함으로서 검사의 결과를 파악하였습니다.