프로그래머스 - 쿼드압축 후 개수 세기Swift(재귀, 분할정복)

쿼드압축 후 개수 세기

문제 설명

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 입니다.

 

입출력 예

arr                                                                                                                                                                                         result

[[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]]	[4,9]
[[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]]	[10,15]

---

입출력 예 설명

입출력 예 #1

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

• 

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

입출력 예 #2

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

• 

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

---

풀이 및 소스코드

처음엔 완전탐색으로 풀어볼 생각을 했다. visited 배열을 선언해 방문해서 방문하지 않았으면 주변을 검사해서 방문하지 않았고 네모면 점점 넓혀가는 식으로.. 하지만 문제는 index가 많아질경우 정확히 4등분이 아닌 중간에서 네모를 만들어 버릴 수 있다.

 

이에 오랜시간 삽질을 하다가 결국 검색했다.

분할 정복 방식이다 재귀..대단하다.

 

첫 xy위치를 기억해두고 범위만큼 검색해나간다.

만약 범위 내에 모두 같은 수라면 해당 수를 +1한다.

하지만 다른 수가 발견된다면 정확히 4등분을 해야하는데, 1사분면, 2사분면, 3사분면, 4사분면을 나누어 x의 범위, y의 범위를 나눈다.

이를 지속적으로 나누어가는데 나누어 가는 방법은 이렇다

총 n의 길이가 8 -> 4 -> 2 -> 1진행되어 나가는 경우의 각 사분면의 범위는 다음과 같다

모든 사분면의 범위는 다음과 같고||||||||x = x..< x+n,   y = y..<y+n ||||||x, y, len의 범위를 각자 지정해주면된다.

x/y	0	1	2	3	4	5	6	7
0	1사	1사	1사	1사	2사	2사	2사	2사
1	1사			1사	2사			2사
2	1사			1사	2사			2사
3	1사	1사	1사	1사	2사	2사	2사	2사
4	3사	3사	3사	3사	4사	4사	4사	4사
5	3사			3사	4사			4사
6	3사			3사	4사			4사
7	3사	3사	3사	3사	4사	4사	4사	4사

x, y, = 0, n = 8

1사분면의 경우 x = x, y = y , n/2 범위만 반으로 좁혀준다

2사분면: x = x, y = y + n/2, n/2  y의 시작범위를 늘려준다x의 범위는 그대로.

3사분면: x = x+n/2, y = y    x의 시작 범위를 늘려준다. y의 범위는 그대로.

4사분면: x = x+n/2, y = y+n/2 x, y 모든 시작 범위를 늘려준다.

 

재귀로 위의 범위를 지속적으로 나누어 탐색해준다. 여기까진 이해가 쉬울 것..

여기서 고민이 하나 생겼다. 각 범위의 요소를 탐색하고 끝나면 예를들어 입출력 예 2번에서 0, 2에서 첫 분할을 하고 타고 들어간 재귀가 끝나면? 0, 3으로 또 넘어가는게 아니냐..

재귀를 통한 분할이 지속되다가, 첫 분할이 끝나면 탐색 자체를 멈춰야한다.

모든 사분면으로 나눈 다음 모든 재귀가 끝나면 return시켜버리면 되는 것이다.

 

이 재귀 코드를 이해하는데 너무 오래 걸렸다.

 

요약)

1. 모든 수가 일치하는지 확인한다

2. 틀린 수가 있다면 4분면으로 나눠라

반복

 

4분면의 수가 모두 일치하지 않는다면 결국 arr[x][y] == arr[x][y] 같은 인덱스상의 위치를 비교하므로 1개가 증가될것이며

4분면의 수가 모두 일치할 경우 더이상 나누어 카운트 하지않고 종료된다.

import Foundation

func solution(_ arr:[[Int]]) -> [Int] {
    var n = arr[0].count
    var zerocnt = 0
    var onecnt = 0   
    func recursion(_ x: Int, _ y: Int, _ len: Int){
        var start = arr[x][y]
        
        for i in x..<x+len{
            for j in y..<y+len{
                if arr[i][j] != start{
                    let half = len/2
                    recursion(x, y, half)
                    recursion(x, y + half, half)
                    recursion(x + half, y, half)
                    recursion(x + half, y + half, half)
                    
                    return
                }
            }
        }
        
        if start == 1{
            onecnt += 1
        }else{
            zerocnt += 1
        }
    }
    
    recursion(0, 0, n)
    
    return [zerocnt, onecnt]
}