[백준][Python]1780번(종이의 개수)

백준 1780번

최종 제출 코드

import sys

N = int(sys.stdin.readline())
paper = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
minus, zero, one = 0, 0, 0   

def solution(x, y, N):   
  global minus, zero, one
  color = paper[x][y]    
  for i in range(x, x+N):    
    for j in range(y, y+N):
      if color != paper[i][j]:    
        next_n = N//3
        solution(x, y, next_n) 
        solution(x+next_n, y, next_n) 
        solution(x+(next_n*2), y, next_n) 
        solution(x, y+next_n, next_n) 
        solution(x, y+(next_n*2), next_n) 
        solution(x+next_n, y+next_n, next_n) 
        solution(x+(next_n*2), y+next_n, next_n) 
        solution(x+next_n, y+(next_n*2), next_n) 
        solution(x+(next_n*2), y+(next_n*2), next_n) 
        return

  if color == 0:    
    zero += 1
  elif color == 1:
    one += 1
  elif color == -1:
    minus += 1

solution(0, 0, N)
print(f'{minus}\n{zero}\n{one}')

코드출처

◼️ 분할 정복으로 풀이

• 분할된 좌표가 같은 숫자로 차 있을때까지 9등분하기를 반복
• 분할된 좌표 내에 다른 숫자가 1개라도 존재한다면 그 상태에서는 숫자를 세는 것이 무의미
  => 좌표를 9등분하여 재귀함수 실행
• 분할된 좌표 내에 숫자가 모두 동일하다면 그 동일한 숫자의 크기를 1 증가시킴