문제

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

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

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

www.acmicpc.net/problem/1780

  • 입력

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

  • 출력

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

최종 코드

처음 풀어보는 분할정복 문제였다. 잘 모르겠어서 인터넷으로 답을 검색했다. 분할정복 알고리즘은 보통 재귀 함수를 통해 구현한다. 이 문제도 마찬가지로 재귀함수를 통해 구현하는 문제였다.

현재의 종이를 검사하고, 9등분해서 다시 각각의 종이를 검사하는 재귀 함수를 구현해야 한다. 따라서 현재의 종이가 하나의 숫자로만 채워져있지 않다면 종이를 9등분해서 재귀함수를 9번 호출하는 방식으로 구현했다.

import sys

def dnc(x, y, n):
    std = arr[x][y]
    for i in range(x, x+n):
        for j in range(y, y+n):
            if arr[i][j] != std:
                n //= 3
                # 종이를 9등분해서 dnc를 9번 호출
                dnc(x, y, n)
                dnc(x, y + n, n)
                dnc(x, y + n * 2, n)
                dnc(x + n, y, n)
                dnc(x + n, y + n, n)
                dnc(x + n, y + n * 2, n)
                dnc(x + n * 2, y, n)
                dnc(x + n * 2, y + n, n)
                dnc(x + n * 2, y + n * 2, n)
                return
    ans[std+1] += 1

n = int(sys.stdin.readline().strip())
arr = []
for _ in range(n):
    arr.append(list(map(int, sys.stdin.readline().split())))

ans = [0, 0, 0]
dnc(0, 0, n)
print(*ans, sep="\n")

참고 사이트