프로그래머스[JS] > 쿼드압축 후 개수 세기

🔥문제링크

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

프로그래머스

 

🔥풀이 핵심

어떤영역이 4분할 될 시 그 각각의 4분할 된 영역을 새로운 영역으로 잡아서 다시 같은 동작을 반복하는 프로세스를 코드로 작성하는게 핵심인데 재귀함수를 이용해서 풀었다.    

 

🔥풀이

일단 0,1 을 count 할 수 있는 객체를 생성한다.

dfs라는 함수를 정의하고 이를 재귀적으로 이용하여 0, 1 을 카운트하였다. 

dfs를 살펴보자.. 

압축해야할 어떤영역의 가장 좌측상단의 row index와 column index를 각각 나는 x, y라 설정하였고 해당 영역 한변의 길이를 l로 잡았다. 처음에 그 영역의 모든 값이 동일 한지 이를 판단하고 만약 동일하다면 (set.size===1) 해당 압축과정을 return을 통해 종료하고 만약 같지 않다면 4분할을 하여 각각의 영역을 다시 압축가능한지 확인하는 과정을 반복한다. 만약 l의 길이가 1이라면 4등분을 더 이상 할 수 없으므로 해당 과정을 종료한다. 

function solution(arr) {
    
    let answer = {
        0:0,
        1:0
    }
    
    let dfs = (x,y,l) =>{
        // 더이상 분할 못할 시 
        if(l===1){
            ++answer[arr[x][y]]
            return
        }
        
        // 모두 같은지 확인 
        let set = new Set([])
        for(let i=x; i<=x+l-1; ++i){
            let sliced = arr[i].slice(y,y+l)
            sliced.forEach((n)=>set.add(n))
        }
        if(set.size===1){
            let n = [...set][0]
            ++answer[n]
            return
        }else{
           // 아닐 시 다시 4조각 
           dfs(x,y+l/2,l/2) //우상
           dfs(x,y,l/2) //좌상
           dfs(x+l/2,y,l/2,l/2) //좌하
           dfs(x+l/2,y+l/2,l/2) //우하
        }  
        return
    } 
    
    dfs(0,0,arr.length)
    
    return [answer[0],answer[1]];
}