쿼드압축 후 개수 세기

문제 안내

문제 설명

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

입출력 예

풀이

Code

# arr를 입력받아 시작지점부터 탐색하며 쿼드압축을 수행하는 함수
# x, y : 시작 지점 / l : 주어진 arr의 한 변의 길이
def quad(arr, x, y, l):
    # 전체 행에 대해 반복
    for i in range(x, x + l):
        # 전체 열에 대해 반복
        for j in range(y, y + l):
            # 탐색하는 i행j열의 값이 시작 지점의 값과 다른 경우
            if arr[i][j] != arr[x][y]:
                # 변의 길이를 2등분
                l = l // 2
                # 주어진 arr를 4등분 하였을 때, 좌상단의 영역에 대해 작업을 계속 반복
                quad(arr, x, y, l)
                # 주어진 arr를 4등분 하였을 때, 좌하단의 영역에 대해 작업을 계속 반복
                quad(arr, x, y + l, l)
                # 주어진 arr를 4등분 하였을 때, 우상단의 영역에 대해 작업을 계속 반복
                quad(arr, x + l, y, l)
                # 주어진 arr를 4등분 하였을 때, 우하단의 영역에 대해 작업을 계속 반복
                quad(arr, x + l, y + l, l)
                return
    
    # 시작지점의 값에 따라 answer 리스트의 해당 위치에 개수를 1씩 늘려줌
    answer[arr[x][y]] += 1

def solution(arr):
    # 재귀 호출을 위해 전역 변수 선언
    global answer
    # 최종적으로 남는 0의 개수와 1의 개수를 담을 배열을 answer 변수에 할당
    answer = [0, 0]

    # arr의 모든 요소를 다 살펴봐야 하기 때문에, 시작 지점을 (0, 0)으로 지정
    quad(arr, 0, 0, len(arr))

    return answer