[🥈2 / 백준 1780 / 파이썬] 종이의 개수

 

1780번: 종이의 개수

 

문제

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

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

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

입력

첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

출력

첫째 줄에 -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

 

풀이

 

쿼드트리와 비슷하지만 4분할이 아닌 9분할을 하면 되는 문제이다.

 

import sys
input = sys.stdin.readline
n = int(input())
square = [list(map(int,input().split())) for i in range(n)]
a,b,c = 0,0,0

def dac(data,x,y,size):
    first_node = data[y][x]
    for i in range(y,y+size):
        for j in range(x,x+size):
        	# 다른 데이터가 존재한다면
            if data[i][j] != first_node:
                break
        else:
            continue
        break
        
    # 단일 데이터 종류로 구성되었다면
    else:
        global a,b,c
        if first_node == -1:
            a += 1
        elif first_node == 0:
            b += 1
        else:
            c += 1
        return 
    # 종류에 따라 값을 증가
    
    # 단일 데이터가 아니기 때문에 분할 정복 실행
    div = size//3
    for i in range(3):
        for j in range(3):
            dac(data, x+i*div, y+j*div, div)
    
dac(square,0,0,n)
print(a,b,c,sep="\n")