실버2 색종이 만들기(2630)

2630번: 색종이 만들기

분할 정복 공부하면서 이렇게 4개로 나눠지는 형태를 쿼드트리라는 것을 처음 알았다. 이렇게 4분할 해서 재귀를 돌리는 형태의 코드가 많이 나왔다. 

import sys
input = sys.stdin.readline

def divide(r, c, n):
  check, flag = matrix[r][c], True
  for i in range(r, r+n):
    for j in range(c, c+n):
      if check != matrix[i][j]:
        flag = False
        n //= 2
        divide(r, c, n)
        divide(r, c+n, n)
        divide(r+n, c, n)
        divide(r+n, c+n, n)
        return 0
  if flag: result[check] += 1

n = int(input())
matrix = [list(map(int, input().split())) for _ in range(n)]
result = {0:0, 1:0}

divide(0, 0, n)
print(result[0])
print(result[1])

처음에는 각 4분면을 나누고 브루트포스로 검색해서 다르면 또 4분면을 나누어가며 재귀를 나타내는 방법으로 풀려고 했다. 하지만 이런 방법은 아무리 생각해도 너무 비효율적인 코드였다. 그러다 생각해보니 첫번째에 전부 1이거나 0이면 1로 출력해야한다는 것이 생각나서 "전체를 탐색하고 다른게 나오면 4분할 한다"라는 생각으로 구현했다. 그리고 result를 딕셔너리로 구현했고, flag를 세워서 다른게 있으면 증가하지 않게 만들었다. 여기서 가장 중요했던 건 아무래도 return을 하는 것이였다. return을 하지 않아서 자꾸 다른 답이 나오고 계속 탐색을 이어나갔기 때문이다.