[PS, Algorithm] - 쿼드압축 후 개수 세기(코딩테스트 연습, LEVEL 2)

📒문제

📢풀이

이틀 전에 3시간을 들였는데도 잘 안되서 포기했다가 오늘 다시 푼 문젠데.... 20분만에 풀었다.

전에 짠 코드랑 뭐가 다른지 모르겠지만ㅠㅠ 그래도 내가 어려워하는 재귀로 만족스럽게 푼 것 같아 기분은 좋다.

def solution(arr):
    def compress(rowS, colS, size):
        if size == 1: return
           
        T = arr[rowS][colS]
        
        able = True
        for i in range(rowS, rowS+size):
            for j in range(colS, colS+size):
                if arr[i][j] != T:
                    able = False
                    break
            if able == False: break
            
        if able:
            result[T] -= (size*size-1)
            return
        else:
            compress(rowS, colS, size//2)
            compress(rowS+size//2, colS, size//2)
            compress(rowS, colS+size//2, size//2)
            compress(rowS+size//2, colS+size//2, size//2)
    
    N = len(arr[0])
    global result
    result = {0: 0, 1: 0}
        
    for i in range(N):
        for j in range(N):
            if arr[i][j] == 0: result[0] += 1
            else: result[1] += 1
    
    compress(0, 0, N)
    
    return list(result.values())
    

📒유사문제 (백준 2630. 색종이 만들기(Silver II))

그냥 처음부터 끝까지 똑같은 문제였다. 이 문제를 풀었던 기억을 살려서 문제를 풀었다 ㅎㅎ

import sys

def solve(rStart, cStart, size):
  
  if size == 1:
    result[arr[rStart][cStart]] += 1
    return

  isPaper = True
  for i in range(rStart, rStart+size):
    for j in range(cStart, cStart+size):
      if arr[i][j] != arr[rStart][cStart]:
        isPaper = False
        break
    if not isPaper:
      break
  
  if isPaper:
    result[arr[rStart][cStart]] += 1
    return

  else:
    solve(rStart, cStart, size//2)
    solve(rStart+size//2, cStart, size//2)
    solve(rStart, cStart+size//2, size//2)
    solve(rStart+size//2, cStart+size//2, size//2)
  

N = int(sys.stdin.readline())
arr = []

for _ in range(N):
  arr.append(list(map(int, sys.stdin.readline().split())))


result = [0, 0]
solve(0, 0, N)

print(result[0])
print(result[1])