[백준 2630] 색종이 만들기 (Python)

2630번: 색종이 만들기

from sys import stdin
n = int(stdin.readline())
graph = [list(map(int, stdin.readline().split())) for _ in range(n)]

white, blue = 0, 0
def get_block(x,y,n) :
  global white, blue
  color = graph[x][y]
  for i in range(x, x+n):
    for j in range(y, y+n) :
      if color != graph[i][j] :
        get_block(x, y, n//2)
        get_block(x+(n//2), y, n//2)
        get_block(x, y+(n//2), n//2)
        get_block(x+(n//2), y+(n//2), n//2)
        return
  if color == 0 :
    white += 1
  else :
    blue += 1

get_block(0,0,n)
print(white)
print(blue)

 이번 문제는 '쿼드 트리'라는 개념을 다루는 문제다. 트리의 자식 노드가 4개씩 분할하는 방법을 의미한다.

같은 색을 가진 영역만 확인하기 때문에, 첫 번째 위치 그래프의 색을 확인해서 같은지 아닌지를 확인하는 과정을 재귀 함수를 통해 할 수 있다.