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

dfs 문제입니다.

 

문제의 핵심은 재귀를 돌면서, 크기가 1일때 까지 4등분을 하는 것입니다.

단, 4등분을 하기 전에 해당 크기의 정사각형 내부가 같은 수로만 이뤄졌다면 4등분을 하지 않습니다.

 

4등분 할 때, 아래의 그림을 참고하시면 됩니다.

 

[구현 코드]

import java.util.*;

class Solution {
    final int[] dx = {-1, 1, 0, 0};
    final int[] dy = {0, 0, -1, 1};
    
    public int[] solution(int[][] arr) {
        int[] answer = {};
        
        int n = arr.length;
        
        dfs(arr, 0, 0, n, n);
        
        // 개수 세기
        int zero = 0;
        int one = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(arr[i][j] == 0){
                    zero++;
                }else if(arr[i][j] == 1){
                    one++;
                }
            }
        }
        
        answer = new int[]{zero, one};
        
        return answer;
    }
    
    void dfs(int[][] arr, int x1, int y1, int x2, int y2){
        if(x2-x1 == 1 && y2 - y1 == 1) return; // 크기가 1이 되면 return
        
        boolean isAllSameNumber = isSame(arr, x1, y1, x2, y2);
        
        if(isAllSameNumber){
            // 같은 수들로만 이루어 졌으면, 첫 수를 제외하고 -1로 치완함
            for(int i=x1; i<x2; i++){
                for(int j=y1; j<y2; j++){
                    if(i == x1 && j==y1) continue;
                    arr[i][j] = -1;
                }
            }
        }else{
            int len = (x2-x1)/2;
            // 4등분
            dfs(arr, x1, y1, x1+len, y1+len);
            dfs(arr, x1, y1+len, x1+len, y2);
            dfs(arr, x1+len, y1, x2, y1+len);
            dfs(arr, x1+len, y1+len, x2, y2);
        }
    }
    
    // 범위 내부의 수들이 같은 수만 있는지 확인
    boolean isSame(int[][] arr, int x1, int y1, int x2, int y2){
        Queue<int[]> qu = new LinkedList<>();
        qu.add(new int[]{x1, y1});
        boolean[][] visited = new boolean[arr.length][arr.length];
        visited[x1][y1] = true;
        
        while(!qu.isEmpty()){
            int[] cn = qu.poll();
            int cx = cn[0];
            int cy = cn[1];
            
            if(arr[x1][y1] != arr[cx][cy]) return false;
            
            for(int i=0; i<4; i++){
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                
                if(!(nx>=x1 && nx<x2 && ny>=y1 && ny<y2)) continue;
                if(visited[nx][ny]) continue;
                
                visited[nx][ny] = true;
                qu.offer(new int[]{nx, ny});
            }
        }
        
        return true;
    }
}