문제

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

풀이

divAndCon 함수의 매개변수로 사각형의 왼쪽 위 꼭짓점의 좌표와 사각형의 한 변의 길이를 받는다.

꼭짓점의 숫자를 temp에 저장한 뒤에 사각형의 칸들을 이중 for문을 통해 돌면서 해당 칸의 숫자가 temp와 같은지 확인한다. 만약에 같지 않다면 tf에 False를 대입하고 for문을 빠져나온다.

tf의 값이 만약에 True라면 temp에 저장된 값에 따라서 result의 값을 +1 해준다.

tf의 값이 만약에 False라면 사각형을 9등분 한 뒤에 9개의 사각형의 왼쪽 위 꼭짓점의 좌표와 한 변의 길이를 divAndCon 함수에 매개변수로 넣어준다. 즉, 재귀를 통해 분할 정복을 하는 풀이이다.

from sys import stdin

n = int(stdin.readline())
paper = []

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

result = [0,0,0]

def divAndCon(x,y,length):
    temp = paper[x][y]
    tf = True
    for i in range(x, x + length):
        for j in range(y, y + length):
            if paper[i][j] != temp:
                tf = False
                break
        if tf == False:
            break
    if tf:
        if temp == -1:
            result[0] += 1
        elif temp == 0:
            result[1] += 1
        else:
            result[2] += 1
    else:
        divLength = length//3
        for i in range(3):
            for j in range(3):
                divAndCon(x + divLength * i, y + divLength * j, divLength)

divAndCon(0,0,n)

for i in result:
    print(i)