BOJ 1780 - 종이의 개수

문제 링크

문제#

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

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

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

입력#

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

출력#

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

풀이#

현재 종이가 전부 같은 수로 채워져 있으면 그 종이 한 장으로 끝내고, 아니면 같은 크기의 작은 종이들로 나눠 다시 확인하면 된다. 그래서 재귀적인 분할 정복이 정답과 아주 잘 맞는다.

이 문제는 3×3으로 쪼개면서 -1, 0, 1 종이 개수를 세고, 색종이 만들기는 2×2로 쪼개며 흰색과 파란색 개수를 센다는 차이만 있다. 구조 자체는 완전히 같은 편이다.

전체를 한 번에 세려 하지 말고, '같으면 멈추고 다르면 쪼갠다'는 규칙만 유지하면 된다. 분할 기준이 보이는 순간 풀이가 정리된다.

코드#

#include <iostream>
using namespace std;
 
int arr[2188][2188];
int answer[3];
 
void solve(int s, int e, int n) {
	int paper = arr[s][e];
	bool not_same = false;
 
	for (int i = s; i < s + n; i++) {
		for (int j = e; j < e + n; j++) {
			if (paper != arr[i][j]) {
				not_same = true;
				break;
			}
		}
		if (not_same)
			break;
	}
 
	if (not_same) {
		int next = n / 3;
 
		for (int k = 0; k < 3; k++) {
			for (int l = 0; l < 3; l++) {
				solve(s + next * k, e + next * l, next);
			}
		}
	}
	else {
		answer[paper + 1]++;
	}
}
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	int n;
	cin >> n;
 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			cin >> arr[i][j];
	}
 
	solve(0, 0, n);
 
	cout << answer[0] << '\n' << answer[1] << '\n' << answer[2] << '\n';
 
	return 0;
}

복잡도#

• 시간 복잡도: 각 분할 단계에서 영역을 검사하므로 최악의 경우 $O(N^2 \log N)$이다.
• 공간 복잡도: 입력 종이와 재귀 스택을 사용하므로 $O(N^2)$이다.

마무리#

같은 수면 바로 세고, 아니면 9등분하는 재귀가 문제 구조와 정확히 맞아떨어진다.