프로그래머스 스쿨(Java - Lv.2) - 쿼드압축 후 개수세기[조건이 달린 재귀함수/DFS]

문제

 

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

프로그래머스

 

 

해답

 

import java.util.*;

class Solution {
    int[][] arr;
    HashMap<Integer,Integer> m = new HashMap<>();
    public int[] solution(int[][] arr) {
        m.put(0,0);
        m.put(1,0);
        this.arr = arr;
        int length = arr.length;
        
        if(bQuad(0,0,length)){
            m.put(arr[0][0],m.get(arr[0][0])+1);
            return new int[]{m.get(0),m.get(1)};
        }
        
        rpt(0,0,length);
        
        return new int[]{m.get(0),m.get(1)};
    }
    
    public void rpt(int R, int C,int length){
       if(length==1)
           m.put(arr[R][C],m.get(arr[R][C])+1);
        
        int[] dR = {R, R+length/2, R, R+length/2};
        int[] dC = {C, C, C+length/2, C+length/2};
        
        for(int i=0;i<4;i++){
            if(bQuad(dR[i],dC[i],length/2)) m.put(arr[dR[i]][dC[i]],m.get(arr[dR[i]][dC[i]])+1);
            else rpt(dR[i],dC[i],length/2);
        }
    }
    
    public boolean bQuad(int x, int y, int len){
        for(int i=x;i<x+len;i++){
            for(int j=y;j<y+len;j++){
                if(arr[x][y]!=arr[i][j])
                    return false;
            }
        }
        
        return true;
    }
}

 

 

해설

 

재귀함수를 쓰는것이 맞는 문제인것으로 보였다.

 

그런데 여기에서 두가지 관점으로 문제 시도를 해 보았는데,

 

첫번째는 

 

이 순서로 코드를 짜는것이고 

 

두번째는 이의 역순으로 짜려고하였다.

 

역순을 먼저 시도하였으나, 시간복잡도와 개수의 문제로 상당히 복잡해져

 

이것은 한 구역을 정하고 모두 같지 않을경우 그 구역을 다시 4개로 분리하여 처리하는 방법을 사용해야한다 깨닫고

 

시작자리, 시작자리+길이/2 이런식으로 각 네모의 왼쪽상단지점의 좌표를 찾아 다시 순회하며 나누어가며 처리하도록 하였으며, 그 재귀의 끝은 길이가 1칸이 되어 더이상 나눌수 없을때로 처리하였다.