[1780] 종이의 개수

😲 문제

출처
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

(1). 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
(2). (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

입력
9
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
0 1 -1 0 1 -1 0 1 -1
0 -1 1 0 1 -1 0 1 -1
0 1 -1 1 0 -1 0 1 -1

출력
10
12
11

❗️ 문제 재정의

문제는 친절히도 두 단계로 나누어져 있다.

1. 지금 검사하려는 부분이 같은 수로 이루어져 있는가? check_paper(x,y,size)
2. 아니라면 9개로 찢고 다시 부분마다 검사한다. divide_paper(x,y,new_size)

중요한 것은 "size, x,y를 어떻게 전달할 것인가?" 이다.
각 부분마다의 시작위치(x,y)를 전달하고 해당 부분의 사이즈(3의 배수형태)를 전달하면 된다.

✔ 계획 수립

1. 주어진 종이가 모두 같은 숫자로 이루어져 있는지 확인
   1. 만약 그렇다면 해당 숫자의 종이 개수를 증가
   2. 만약 종이가 같은 숫자로만 이루어져 있지 않다면, 종이를 9개의 동일한 크기의 부분으로 나눈다. (각 부분에 대해 재귀적으로 동일한 과정을 반복)
2. 이 과정을 모든 부분 종이에 대해 반복하고, -1, 0, 1로 이루어진 종이의 개수를 각각 세어 결과를 출력

👨🏻‍💻 문제 풀이

n = int(input())
paper = [list(map(int,input().split())) for _ in range(n)]
result = {-1:0,0:0,1:0}

def check_paper(x, y, size):
    paper_type = paper[x][y]
    for i in range(x, x+size):
        for j in range(y, y+size):
            if paper_type != paper[i][j]:   
                return False
    return True
    
def divide_paper(x, y, size):
    if check_paper(x,y,size):
        result[paper[x][y]] += 1
    else:
        new_size = size//3
        for i in range(3):
            for j in range(3):
                divide_paper(x+i*new_size,y+j*new_size,new_size)
                
divide_paper(0,0,n)
print(result[-1])
print(result[0])
print(result[1])

😅 회고

분할정복의 정석인듯 싶다.
솔직히 모든 재귀가 나에게 그렇지만 풀이를 한번에 생각해내기 어려웠다.