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

문제설명
NxN 크기의 배열에 숫자 0과 1이 있을때, 어느 숫자 MxM의 범위의 숫자가 모두 같은 구역의 수를 구하는 문제입니다.(M은 2의 배수와 1 중 하나이고 2*2 범위의 숫자가 모두 같을 경우 그 범위는 더 이상 탐색하지 않습니다.)

작동 순서
1. 배열의 크기 N을 입력받습니다.
2. 배열의 숫자들을 입력받습니다.
3. 배열을 탐색하여 모든 숫자가 1이거나 0인 경우 해당 구역을 숫자가 모두 같은 범위로 인식하고 그에 맞는 값을 반환합니다.
4. 배열을 탐색하였는데 모든 숫자가 같지 않은 경우 해당 배열을 4등분하여 다시 탐색합니다.
5. 모든 탐색이 끝나면 1로 이루어진 범위의 수와 0으로 이루어진 범위의 수를 출력합니다.

소스코드

import sys


def searchPaper(paperArr, N):
    paperSum = 0
    for h in range(N):
        paperSum += sum(paperArr[h])
    if paperSum == N**2:
        return [1]
    elif paperSum == 0:
        return [0]
    else:
        cut1 = []
        cut2 = []
        cut3 = []
        cut4 = []
        for h in range(0, N//2):
            cut1.append(paperArr[h][0:N//2])
            cut3.append(paperArr[h][N//2:N])
        for h in range(N//2, N):
            cut2.append(paperArr[h][0:N//2])
            cut4.append(paperArr[h][N//2:N])
        return searchPaper(cut1, N//2)+searchPaper(cut2, N//2)+searchPaper(cut3, N//2)+searchPaper(cut4, N//2)


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

blue = 0
white = 0
result = searchPaper(paper, N)
for i in range(len(result)):
    if result[i] == 1:
        blue += 1
    else:
        white += 1
print(white)
print(blue)

후기
문제를 풀 때 계속해서 효율성이 떨어지는 것 같습니다. 공간 복잡도나 시간 복잡도를 줄이는 것을 더욱 더 신경쓰면서 코딩하는 법을 공부해야 할 것 같습니다.