문제 이해

여러 개의 정사각형칸들로 이루어진 정사각형 모양 종이가 주어진다.

이 종이에는 1과 0값으로 값이 설정되어 있다.

이 때 $N\times N$ 형식인 정사각형 안에 같은 색깔만 존재하도록 정사각형 모양 종이를 자르고 싶다(N = $2^k$)

자르는 규칙은 아래 사진과 같다

위 방식으로 정사각형을 만들 때 0으로 이루어진 정사각형 종이 개수, 1으로 이루어진 정사각형 종이 개수를 차례로 출력하는 문제이다.

---

문제 풀이

Brute-force밖에 해결 방법이 생각나지 않았다.

만약 정사각형을 하나 설정하고 같은 색깔이 아니라면 재귀 함수를 통해 총 4개 부위로 나눈 뒤, 각 재귀함수에서 또 해당 정사각형 색종이가 같은 색으로 이루어져있는지 확인하는 식으로 코드를 짜야겠다고 생각했다

---

코드

N = int(input())

arr = []
for i in range(N):
    arr.append(list(map(int,input().split())))

result = []
one = 0
def find(x,y,length):
    color = arr[x][y]
    # arr[x][y]가 정사각형 색종이 중 가장 왼쪽 위에 존재하는 값이다
    # 만약 정사각형이 모두 같은 색깔이라면 다른 값들도 이 값과 동일한
    # 값을 가져야 한다.
    for i in range(x, x+length):
        for j in range(y, y+length):
            if color!=arr[i][j]:
                # 위에서 지정했던 color와 다른 색깔이 존재하는 상황이다
                # 정사각형 종이를 총 4개 부위로 잘라 4개 부위에 대하여
                # 재귀함수를 실행시킨다
                find(x,y,length//2)
                find(x,y+length//2,length//2)
                find(x+length//2,y,length//2)
                find(x+length//2,y+length//2,length//2)
                return

	# 여기까지 왔다면 for문에서 return 문구가 실행되지 않았다는 것이다
    # 즉, 이번 재귀함수가 실행되었을 때 정사각형 색종이는 모두 같은 색으로
    # 이루어져 있으므로, color 값을 결과 행렬에 더해준다.
    if color==0:
        result.append(0)
    else:
        result.append(1)

find(0,0,N)

print(result.count(0)) # result 배열에서 값이 0인 개수 출력
print(result.count(1)) # result 배열에서 값이 1인 개수 출력

---

결과