[Python] 종이의 개수 - 백준 (분할정복)

해당 글은 백준 1780번 '종이의 개수' 문제를 다룬다.

문제

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

1780번: 종이의 개수

 

설명

이전에 풀었던 분할정복 알고리즘 문제인 쿼드트리와 같지만, 2개가 아닌 3개로 분할하는 것만 다르다.

마찬가지로 분할될 때의 가장 왼쪽 위의 값과 같은 분할 안의 값이 같은지 확인하는 방법으로 진행하였다.

즉, 첫 번째 nxn 행렬에서는 (0, 0)의 값과 다른 위치의 값들을 비교한다.

 

코드

import sys
input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
result = [0, 0, 0]

def check(x, y, n):
    for i in range(x, x+n):
        for j in range(y, y+n):
            if arr[x][y] != arr[i][j]:
                n //= 3
                for k in range(3):
                    for l in range(3):
                        check(x+k*n, y+l*n, n)
                return
    if arr[x][y] == -1:
        result[0] += 1
    elif arr[x][y] == 0:
        result[1] += 1
    else:
        result[2] += 1

check(0, 0, n)
for i in result:
    print(i)