백준 1780번: 종이의 개수

https://www.acmicpc.net/problem/1780

쿼드트리의 문제인데 9등분 하고, 1과 0 이외에 -1도 압축하는 문제이다.

풀이 및 해답

import sys
input = sys.stdin.readline

N = int(input())
lst = [list(map(int, input().split())) for _ in range(N)]

result = { -1: 0, 0: 0, 1: 0 }

def conquer(n, lst):
    values = set()
    for row in lst:
        values.update(row)

    # 모두 같은 수면 result에 추가
    if len(values) == 1: # 집합 자료형을 이용하여서 모두 같은 지 아닌지 판별
        result[lst[0][0]] += 1
        return

    step = n // 3 # 3등분 해줌

    # 3x3으로 나눠서 재귀 호출
    for i in range(0, n, step):           # 행 기준
        for j in range(0, n, step):       # 열 기준
            # (i, j) 위치에서 시작하는 step x step 부분 잘라서 넘기기
            sub_lst = [row[j:j+step] for row in lst[i:i+step]]
            conquer(step, sub_lst)

conquer(N, lst)

print(result[-1])
print(result[0])
print(result[1])