[프로그래머스] 쿼드압축 후 개수 세기 (level2, python)

문제 설명

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

---

풀이 코드

def check(start, size, arr):
    global answer
    x, y = start
    # size 1인 정사각형의 경우
    if size == 1:
        if arr[x][y]:
            answer[1] += 1
        else:
            answer[0] += 1
        return
    
    # size인 정사각형 내부가 모두 동일한 원소인지 체크
    temp = arr[x][y]
    flag = True
    for i in range(size):
        for j in range(size):
            nx = x + i
            ny = y + j
            if temp != arr[nx][ny]:
                flag = False
                break
                
    # 아닌 경우 4조각으로 쪼개기
    if flag:
        if temp:
            answer[1] += 1
        else:
            answer[0] += 1
        return
    else:
        next = size // 2
        check([x, y], next, arr)
        check([x, y+next], next, arr)
        check([x+next, y], next, arr)
        check([x+next, y+next], next, arr)
        return
        

def solution(arr):
    global answer
    answer = [0, 0]
    
    size = len(arr)
    check([0, 0], size, arr)
    
    return answer

분할정복 문제이다. 백준 기준으로는 실버 1~2 정도의 난이도.

N 사이즈의 정사각형을 4분할하여 내부 원소가 모두 동일하면 하나로 계산하는 그런 문제이다.

 

재귀를 사용해서 풀이해야 한다는 것만 알고 있으면 쉽게 풀이할 수 있다.

1) 정사각형의 사이즈가 1이면 기저 조건 (재귀를 멈추기 위한 최소 조건)

2) 내부 정사각형의 원소가 모두 동일한 원소면 재귀로 들어가지 않고 결과만 반영

3) 그게 아니라면, 정사각형을 다시 4분할 해 각각의 정사각형에 대해 다시 판단.