프로그래머스(Java) - 쿼드압축 후 개수

문제 링크

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

문제 풀이

DFS를 이용하여 길이를 절반씩 줄여가면 4분할한다.
최초의 길이가 arr.length 라면 처음 쿼드의 길이는 arr.length/2
그 다음 쿼드의 길이는 (arr.length/2)/2 이다.
가장 최소의 쿼드인 1이 될때까지 반복한다.

int res = dfs(0,0,arr.length);

1인 쿼드의 4개의 값이 모두 같다면 그 값을 return 하고, 하나라도 다른 값이 있다면 -1을 return 하고, 0의 개수만큼 result[0]에, 1의 개수만큼 result[1]값에 더해준다.

        if(len==1){
            if(map[y][x]==map[y][x+1] && map[y][x]==map[y+1][x] && map[y][x]==map[y+1][x+1]){
                return map[y][x];
            }else{
                for(int i=0; i<2; i++){
                    for(int j=0; j<2; j++){
                        result[map[y+i][x+j]]++;
                    }
                }
               return -1; 
            }
        }

길이가 1인 쿼드에 가지전에 길이가 2인 쿼드를 거쳐야 하는데 이때는 4분할 하지않고 길이만 줄여서 len=1을 만들어주고 다음 재귀로 보낸다.

else if(len==2){
            return dfs(y,x,len/2);
        }

나머지 구간에서는
각각의 4분할한 영역의 좌측상단을 기준으로 dfs로 재귀를 돌린다.
해당 dfs가 -1이라는 것은 쿼드가 하나로 합쳐지지 못했다는 뜻이다.
그래서 dfs의 결과값인 yx가 -1이 아니며 yx와 나머지 분할한 쿼드들의 값이 같으면 하나로 합친다. 아닌경우에는 합쳐지지 않았다는 뜻이므로 result[0], result[1]에 더해준다.

else{
            len /=2;
            int yx = dfs(y,x,len);
            int yx1 = dfs(y,x+len,len);
            int y1x = dfs(y+len, x, len);
            int y1x1 = dfs(y+len, x+len, len);
            if(yx!= -1 && (yx==yx1 && yx==y1x && yx==y1x1)){
                 return map[y][x];
            } else{      
                if(yx>=0){
                    result[yx]++;
                }
                if(yx1>=0){
                   result[yx1]++;
                }    
                if(y1x>=0){
                    result[y1x]++;
                }         
                if(y1x1>=0){
                   result[y1x1]++;
                }
                return -1;
            } 
 }

---

코드

class Solution {
    
    static int [][] map;
    static int [] result = new int[2];
    public int[] solution(int[][] arr) {
       
        map = arr;
        int res = dfs(0,0,arr.length);
        if(res>=0){
            result[res]++;
        }
        
        int[] answer = result;
        return answer;
    }
    public static int dfs(int y, int x, int len){
        
        if(len==1){
            if(map[y][x]==map[y][x+1] && map[y][x]==map[y+1][x] && map[y][x]==map[y+1][x+1]){
                return map[y][x];
            }else{
                for(int i=0; i<2; i++){
                    for(int j=0; j<2; j++){
                        result[map[y+i][x+j]]++;
                    }
                }
               return -1; 
            }
        }else if(len==2){
            return dfs(y,x,len/2);
        }else{
            len /=2;
            int yx = dfs(y,x,len);
            int yx1 = dfs(y,x+len,len);
            int y1x = dfs(y+len, x, len);
            int y1x1 = dfs(y+len, x+len, len);
                
            if(yx!= -1 && (yx==yx1 && yx==y1x && yx==y1x1)){
                 return map[y][x];
            } else{
                
                if(yx>=0){
                    result[yx]++;
                }
                
                if(yx1>=0){
                   result[yx1]++;
                }
                    
                if(y1x>=0){
                    result[y1x]++;
                }    
                    
                if(y1x1>=0){
                   result[y1x1]++;
                }
                
                return -1;
            } 
                
        }       
    }
}