문제

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

풀이 - 1

분할 정복과 재귀를 사용해서 푸는 문제이다.

풀이 과정은 다음과 같다.

1. 2n x 2n 크기의 색종이가 하나의 색깔로 이루어져 있는지 확인한다.
2. 하나의 색깔로 이루어져 있으면 무슨 색인지 확인한 후에 resultB나 rersultW를 +1 해준다.
3. 하나의 색깔로 이루어져 있지 않으면 n x n 크기의 사각형으로 4등분한다.
4. 1번 ~ 3번 과정을 반복한다.

from sys import stdin

n = int(stdin.readline())

divideList = [[] for i in range(4)]
inputList = []
resultB = 0
resultW = 0

for i in range(n):
    inputList.append(list(map(int,stdin.readline().split())))

def divide(List, k):
    global resultB
    global resultW
    l = [[] for i in range(4)]
    for i in range(k):
        if i < k/2:
            l[0].append(List[i][:k//2])
            l[1].append(List[i][k//2:])
        else:
            l[2].append(List[i][:k//2])
            l[3].append(List[i][k//2:])
    for i in l:
        if check(i, k//2):
            if i[0][0] == 1:
                resultB += 1
            else:
                resultW += 1
        else:
            divide(i, k//2)

def check(checkList, k):
    bw = checkList[0][0]
    tf = True
    for i in range(k):
        for j in range(k):
            if checkList[i][j] != bw:
                tf = False
                break
        if tf == False:
            break
    return tf

if check(inputList, n):
    if inputList[0][0] == 1:
        resultB = 1
    else:
        resultW = 1
else:
    divide(inputList, n)

print(resultW)
print(resultB)

풀이 - 2

문제를 좀 더 깔끔하게 푸는 방법이 있어서 가져왔다.
https://wlstyql.tistory.com/133 이 글을 참고했다.

from sys import stdin

n = int(stdin.readline())
l = []
w_cnt, b_cnt = 0, 0
for i in range(n):
    l.append(list(map(int,stdin.readline().split())))

def divideAndConquer(x,y,N):
    global w_cnt, b_cnt
    tmp_cnt = 0
    for i in range(x, x + N):
        for j in range(y, y + N):
            if l[i][j]:
                tmp_cnt += 1
    if not tmp_cnt:
        w_cnt += 1
    elif tmp_cnt == N * N:
        b_cnt += 1
    else:
        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

divideAndConquer(0,0,n)
print(w_cnt)
print(b_cnt)