백준 2630번 "색종이 만들기"

문제

백준 2630번 "색종이 만들기"

풀이

쿼드트리를 이용한 문제.
계속해서 4개의 단말로 나누어진다고 해서 쿼드트리이다.

배열의 전체를 검사하여 하나라도 틀리면 4개의 분면으로 나누고 재귀를 이용해 반복한다.
1 혹은 0이 정사각형을 이루면 해당 변수에 1을 더해주고 재귀를 멈추고 다른 재귀로 넘어간다.

Python 코드

import sys
input = sys.stdin.readline

def cut(p, n):
  global blue, white
  check = p[0][0]
  ex = False

  for i in range(n):
    if ex:
      break

    for j in range(n):
      if p[i][j] != check:
        cut([row[:n//2] for row in p[:n//2]], n//2)
        cut([row[n//2:n] for row in p[:n//2]], n//2)
        cut([row[:n//2] for row in p[n//2:n]], n//2)
        cut([row[n//2:n] for row in p[n//2:n]], n//2)
        ex = True
        break
    
  if not ex:
    if check == 1:
      blue += 1
    else:
      white += 1

n = int(input())
paper = []
white = 0
blue = 0
for _ in range(n):
  paper.append(list(map(int, input().split())))

cut(paper, n)

print(white)
print(blue)