[1780] 종이의 개수 - 재귀 / 분할 정복 ★★☆☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

 

---

[ 문제 접근 ]

 

문제를 보면 분할 정복인건 알겠고, 재귀를 이용하면 되는거 까지는 쉽게 알 수 있었는데.

코드로 직접 짜보는거는 쉽지 않았다.

 

우선 입력으로 주어진 배열을 받을 전역변수 arr 를 만들어줬고,

 

재귀를 사용 해야하기에 base case 가 뭘지 생각해줬다.

 

색종이가 1개의 원소를 가리킬때가 base case 라는걸 알 수 있었고, 그러기 위해서는 각 단계마다 n은 3배씩 줄어 들어야 함을 알아냈다.

 

이제 재귀함수의 인자로 무엇을 넘겨줄까를 고민해 보았는데, divide 할때마다 행 과 열이 1/3 씩으로 나뉘기에

0 , 3 , 6 처럼 행과 열의 좌표를 3씩 늘어나게끔 해서 총 9번의 재귀함수를 호출했다.

 

---

[ 최종 코드 ]

 

#include<iostream>
#include<vector>
#include<string>
using std::cin; using std::cout;
using std::vector;

int n;
int arr[2188][2188];
int result[3];

void solve(int n,int a,int b){
	if (n == 1) {                 
		result[arr[a][b] + 1]++;//인덱스는 음수 일 수 없기에 전부 +1씩 해준 다음에 배열에 저장.
		return;
	}
	bool is_same = true;
	for(int i=a;i<a+n;i++){
		for (int j = b; j < b+n; j++) {
			if (arr[a][b] != arr[i][j]) {
				is_same = false;
				break;
			}
		}
		if (!is_same)break;
	}
	if (is_same) {
		result[arr[a][b] + 1]++;
		return;
	}
	else {
		int temp = n / 3;
		solve(n / 3, a, b);
		solve(n / 3, a, b+temp);
		solve(n / 3, a, b + 2 * temp);
		solve(n / 3, a + temp, b);
		solve(n / 3, a + temp, b + temp);
		solve(n / 3, a + temp, b + 2 * temp);
		solve(n / 3, a + 2 * temp, b);
		solve(n / 3, a + 2 * temp, b + temp);
		solve(n / 3, a + 2 * temp, b + 2 * temp);
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}
	solve(n,0,0);

	cout << result[0] << '\n' << result[1] << '\n' << result[2];

	return 0;
}

---

[ 다른 사람 코드 ]

 

👉 색종이가 같은 원소라만 이루어져 있는지 확인하는 함수를 따로 만들어줘도 된다.

 

int N;
int paper[2200][2200];
int cnt[3]; //-1, 0, 1로 채워진 종이 갯수

//해당 종이 내부에 같은 숫자로만 채워졌는지 확인하는 함수
bool check(int x, int y, int n) {
  for (int i = x; i < x + n; i++)
  for (int j = y; j < y + n; j++)
    if (paper[x][y] != paper[i][j])
    return false;
  return true;
}
void solve(int x, int y, int z)
{
  if (check(x, y, z)) {
    cnt[paper[x][y] + 1] += 1;
    return;
  }
  int n = z / 3;
  for (int i = 0; i < 3; i++)
  for (int j = 0; j < 3; j++)
    solve(x + i * n, y + j * n, n);
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> N;
  for (int i = 0; i < N; i++)
  for (int j = 0; j < N; j++)
    cin >> paper[i][j];
  solve(0, 0, N);
  for (int i = 0; i < 3; i++) cout << cnt[i] << "\n";
}

 

👉 색종이가 같은 숫자인지 아닌지 판단은 여러가지 방법으로 할 수 있다.

 

#include<bits/stdc++.h>
#define MAX 2333
using namespace std;
int arr[MAX][MAX];
int cnta=0, cntb=0, cntc=0;
int reta=0, retb=0, retc=0;
void f(int y, int x, int size) {
	cnta=0, cntb=0, cntc=0;
	for(int i=y; i<y+size; i++) {
		for(int j=x; j<x+size; j++) {
			if(arr[i][j]==-1) cnta++;
			else if(arr[i][j]==0) cntb++;
			else if(arr[i][j]==1) cntc++;
		}
	}
	if(cnta==size*size) reta++;
	else if(cntb==size*size) retb++;
	else if(cntc==size*size) retc++;
	else {
		f(y, x, size/3); // 왼쪽맨위처음 
		f(y, x+size/3, size/3); // 왼쪽맨위중간 
		f(y, x+size/3*2, size/3); // 왼쪽맨위마지막 
		
		f(y+size/3, x, size/3); // 중간처음 
		f(y+size/3, x+size/3, size/3); // 중간중간 
		f(y+size/3, x+size/3*2, size/3); // 중간마지막 
		
		f(y+size/3*2, x, size/3); // 마지막처음 
		f(y+size/3*2, x+size/3, size/3); // 마지막중간 
		f(y+size/3*2, x+size/3*2, size/3); // 마지막마지막 
	}
	return;
}
int main() {
	int n;
	cin >> n;
	for(int i=0; i<n; i++) {
		for(int j=0; j<n; j++) {
			cin >> arr[i][j];
		}
	}
	f(0, 0, n);
	
	cout << reta << endl << retb << endl << retc;
	
	return 0;
}

---

[ Key Point ]

 

👉 base case 에는 반드시 return 을 써주자.

 

---

[ 다른 사람 풀이 ]

 

ref :: https://velog.io/@minseojo/%EB%B0%B1%EC%A4%80-1780.-%EC%A2%85%EC%9D%B4%EC%9D%98-%EA%B0%9C%EC%88%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-c-%EB%B6%84%ED%95%A0-%EC%A0%95%EB%B3%B5

ref :: https://jaehoon0124welcome.tistory.com/m/20?category=940919