3월 8일 TIL

프로그래머스 코딩테스트 [ 쿼드압축 후 개수 세기 ]

Github 링크

• 이 문제는 쿼드트리를 구현하는 문제다.
• 쿼드트리는 각 내부 노드에 정확히 4개의 자식이 있는 트리 구조이며, 2차원 공간을 재귀적으로 4개의 영역으로 분할하는데 사용된다고 한다.
  (출처: 프로그래머스)
• 위 그림처럼 주어진 영역으로 4개의 영역으로 분할하고, 만약 분할된 영역에 모든 요소들이 같다면 하나의 요소만 남도록 구현한다.
• 처음 이문제를 봤을때 나누는건 그래 어떻게든 나누겠는데, 저걸 어떻게 저장하지?.. 배열로 저게 되나.. dictionary를 써야하나 생각을 했지만. 다시 생각해보면 재귀함수를 사용한다면, 굳이 저장을 해야하나? 라는 생각이 들었다.
• 4개의 영역을 나누고, 나눴을때 x,y 좌표와 사이즈만 전달해준다면, 재귀함수를 통해 구할 수 있을꺼 같다는 생각으로 접근을 했다.
• 재귀 함수 로직은 아래와 같다.

/*
1. 인자로 현재 영역의 왼쪽 최상단의 좌표를 각각 x,y로 받는다, 그리고 해당 영역의 사이즈 또한 인자로 받는다.
2. 해당 영역이 다 똑같은 숫자로 (0 혹은 1) 로 구성되어 있는지 for 문으로 확인한다.
3. 만약 같다면 정답 배열 에서 해당 숫자의 개수를 증가시킨다.
3-1. 해당영역은 하나로 통일된거이기 때문에 return.
4. 다르다면 해당 영역을 4등분 했을때의 newSize를 구한다.
4-1. 예를 들어 4*4 영역인 경우, 4등분 했을때 최상단 좌표는 각각 (0,0), (2,0), (0,2), (2,2)다. 즉 현재 size / 2 를 각각 x,y에 더해주는 것이다.
4-2 변경된 좌표로 총 4번 재귀함수를 호출한다. 그리고 다시 1번부터 반복
*/

import Foundation

func solution(_ arr:[[Int]]) -> [Int] {
    var ans : [Int] = [0,0]
    
    func quadTree(_ x : Int, _ y : Int, _ size : Int){
        let tempNum = arr[x][y]
        var allEqual = true
        
        for i in x..<x+size{
            for j in y..<y+size{
                if arr[i][j] != tempNum{
                    allEqual = false
                    break
                }
            }
            if allEqual == false{
                break
            }
        }
        if allEqual == true {
            ans[tempNum] += 1
        }else{
            let newSize = size / 2
            quadTree(x,y,newSize)
            quadTree(x+newSize,y+newSize,newSize)
            quadTree(x,y+newSize,newSize)
            quadTree(x+newSize,y,newSize)
            
        }
        
    }
    quadTree(0,0,arr.count)
    return ans
}

• 항상 재귀함수 문제를 풀때는 저장을 어떻게 할지도 중요하지만, 재귀함수 과정에서 바로 답을 추출해낼수 있다면, 저장을 할 필요가 없으니 고려하면서 풀어도 좋을꺼 같다.