[백준/C++] 1780번 - 종이의 개수

 

문제

https://www.acmicpc.net/problem/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로만 채워진 종이의 개수를 출력한다.

 

 

풀이

 

이전에 풀었던 색종이 만들기 문제와 완전 똑같았다.

 

색종이 만들기

 

 

풀이 방식도 거의 비슷해서 함수에서 재귀 탐색하는 부분과 개수를 세는 부분만 바꿨다.

 

색종이의 숫자들이 전부 같은지 검사하고 만약 다르다면 3부분씩 총 9부분으로 나눠서 다시 재귀적으로 색종이를 탐색했다.

 

 

 

 

Code

 

 

#include<iostream>
using namespace std;

int N;
int** lst = new int* [N];
int n1_cnt = 0, n2_cnt = 0, n3_cnt = 0;

bool search(int x_st, int x_ed, int y_st, int y_ed) { // 색종이가 전부 같은 숫자인지 검사
	int one_cnt = 0, zero_cnt = 0, div_cnt = 0;
	int flag = lst[y_st][x_st];
	for (int i = y_st; i <= y_ed; i++) {
		for (int j = x_st; j <= x_ed; j++) {
			if (flag!=lst[i][j]) {
				return false;
			}
		}
	}
	if (flag==-1) {
		n1_cnt += 1;
	}
	else if(flag==0) {
		n2_cnt += 1;
	}
	else{
		n3_cnt+=1;
	}
	return true;
}

void dev(int x_st, int x_ed, int y_st, int y_ed) { //만약 숫자가 다르다면 재귀로 탐색
	if (search(x_st, x_ed, y_st, y_ed)) {
		return;
	}
	else {
		int a = (x_ed - x_st+1)/3;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				dev(x_st+i*a, x_st-1 + (i+1)*a, y_st+j*a, y_st-1 + (j+1)*a);
			}
		}
		return;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int atom;
	cin >> N;
	lst = new int* [N];
	for (int i = 0; i < N; i++) {
		lst[i] = new int[N];
		for (int j = 0; j < N; j++) {
			cin >> atom;
			lst[i][j] = atom;
		}
	}
	
	dev(0, N - 1, 0, N - 1);
	cout << n1_cnt << "\n";
	cout << n2_cnt<<"\n";
	cout << n3_cnt;

	for (int i = 0; i < N; i++) {
		delete[] lst[i];
	}
	delete[] lst;
}

 

---

 

재귀로 탐색할때 9부분을 전부 써주는게 낭비라 for문을 이용해 코드의 길이를 줄였다.

 

처음에 범위를 설정할 때, 살짝 헷갈렸는데 확실히 종이에 써보는게 코드 오류를 찾는데 편리한 것 같다.

 

 

 

1780번: 종이의 개수