프로그래머스 쿼드압축 후 개수 세기 Kotlin (dfs,분할 정복)

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/68936

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

문제 설명

0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.

1. 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
2. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
3. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.

arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1, 2, 4, 8, ..., 1024 중 하나입니다.
  • arr의 각 행의 길이는 arr의 행의 개수와 같습니다. 즉, arr은 정사각형 배열입니다.
  • arr의 각 행에 있는 모든 값은 0 또는 1 입니다.

---

입출력 예

---

입출력 예 설명

입출력 예 #1

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.

• 

• 최종 압축 결과에 0이 4개, 1이 9개 있으므로, [4,9]를 return 해야 합니다.

입출력 예 #2

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.

• 

• 최종 압축 결과에 0이 10개, 1이 15개 있으므로, [10,15]를 return 해야 합니다.

풀이

2021.12.11 - [알고리즘 문제 풀이/백준] - 백준 2630 색종이 만들기 Kotlin (dfs,분할 정복)

 

백준의 색종이 만들기 문제와 동일한 문제이다.

분할 정복 기법에 근거하여, 8*8 사이즈의 정사각형을 검사 후, 내부에 1과 0이 공존한다면 완성되지 않았다면 4*4 사이즈 정사각형 4개 검사, 4*4 사이즈의 정사각형 4개 중 3개가 내부에 1과 0이 공존한다면 2*2사이즈의 정사각형을 3*4개 검사, ~~~1*1 정사각형까지 검사하여, 완성된 1 혹은 0으로만 이루어진 정사각형의 개수를 나눠서 출력하면 된다.

dfs 알고리즘을 사용하였다.

 

코드

class Solution {
    
    val answer = IntArray(2){0}
    
    fun dfs(r : Int, c : Int, size : Int, arr : Array<IntArray>){
        var zero = true
        var one = true
        for(i in r until r+size){
            for(j in c until c+size){
                if(arr[i][j]==0) one = false
                if(arr[i][j]==1) zero = false
            }
        }
        if(zero){
            answer[0]++ 
            return
        }
        if(one){
            answer[1]++
            return
        }
        dfs(r,c,size/2,arr)
        dfs(r,c+size/2,size/2,arr)
        dfs(r+size/2,c,size/2,arr)
        dfs(r+size/2,c+size/2,size/2,arr)
        
    }
    
    fun solution(arr: Array<IntArray>): IntArray {
        dfs(0,0,arr.size,arr)
        return answer
    }
}