[알고리즘] Programmers 쿼드압축 후 개수 세기 #Python

[Programmers] 쿼드압축 후 개수 세기 바로가기

📍 문제 설명

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 해야 합니다.

---

📍 문제 풀이

📌 풀이 과정

• 분할 정복(ivide and Conquer) 알고리즘을 활용하였다.
  • 참고한 사이트 : 분할 정복, 풀이 코드

• 재귀를 활용하여 문제를 해결하였다.
  • 처음 주어진 배열이 쿼드 압축이 가능하다면 압축한 후 해당 배열의 원소 값을 1 증가시킨다.
  • 처음 주어진 배열이 쿼드 압축이 불가능하다면,
    • 현재 배열을 4분할하여 다시 쿼드 압축이 가능한지 확인한다.
    • 만약 분할된 배열이 쿼드 압축이 가능하다면 해당 배열의 원소 값을 1 증가시킨다.
    • 만약 분할된 배열이 쿼드 압축이 불가능하다면 해당 배열을 다시 4분할하여 쿼드 압축이 가능한지 확인한다.

• 4분할 한 후 return 의 값을 주는 이유는 현재 배열은 쿼드 압축이 불가능해서 4분할을 진행한 후 코드가 종료되어야 하는데 만약 return 이 존재하지 않는다면 그대로 코드가 진행하여 마치 현재 배열이 쿼드 압축이 가능한 것처럼 answer 의 target 에 대한 값이 1 증가하기 때문에 이를 막기 위해 return 문을 작성한다.

✍ 코드

def solution(arr):
    answer = [0, 0]
    def compress(x,y,n):
        target = arr[y][x]
        for i in range(y,y+n):
            for j in range(x,x+n):
                if target != arr[i][j]:
                    n //= 2
                    compress(x,y,n)
                    compress(x+n,y,n)
                    compress(x,y+n,n)
                    compress(x+n,y+n,n)
                    return 
        answer[target] += 1
    compress(0,0,len(arr))
    return answer