Baekjoon Online Judge 2630번 파이썬. 분할정복

문제 링크
https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

분할 정복은 문제를 나눌 수 없을 때까지 나누어서 각각 풀고 합병하는 방식이다. 함수를 재귀적으로 호출하여 문제를 해결한다는 특징이 있다.

전체 종이를 ‘N//2’ 절반씩 나누어 함수에 넣고 더 이상 나누어지지 않을 때까지 함수를 계속해서 불러왔다.

정답 코드

import sys

N = int(sys.stdin.readline())
whole = [list(map(int, sys.stdin.readline().split())) for i in range(N)] 

result = []

def DivideandConquer(x,y,N):
  color = whole[x][y]
  for i in range(x,x+N):
    for j in range(y,y+N):
      if color != whole[i][j]:
        DivideandConquer(x,y,N//2)
        DivideandConquer(x+N//2,y,N//2)
        DivideandConquer(x,y+N//2,N//2)
        DivideandConquer(x+N//2,y+N//2,N//2)
        return
  if color == 0:
    result.append(0)
  else:
    result.append(1)

DivideandConquer(0,0,N)

print(result.count(0))
print(result.count(1))