백준 1780번: 종이의 개수 (분할정복,재귀)-분할정복의 개념

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

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로만 채워진 종이의 개수를 출력한다.

 

이 문제를 보고 분할정복을 이용한 재귀함수로 풀어야 겠다고 생각이 들었다. 일단 값이 같은지 확인해주는 함수랑 계속 9등분 시키면서 규칙에 맞는 종이를 찾는 재귀함수 2개를 생각했다.

사실 이 문제는 구현의 문제이지 수학적이거나 고민거리가 많지는 않다고 생각했다. 아마 재귀에 익숙하지 않으면 힘들것 같다. 

 

재귀와 분할 정복의 차이

나는 이 문제를 풀면서 생긴 궁금증이 분할정복과 재귀의 차이였다.

분할정복에 보통 재귀를 많이 사용하지만 굳이 차이점을 나눈다면

분할정복은 어떤 문제를 나눌 수 없을 때까지 나누어서 각각을 풀어서 다시 합병하여 문제의 답을 얻는 알고리즘이고 재귀는 단순히 함수가 자신을 참조하는 것을 뜻한다.

코드를 보자(메모리 아끼려면 벡터를 이용했어야 했는데...무지성으로 풀고 나중에 꺠달아버렸다...)(아직 익숙하지 않나 보다...)

#include <iostream>
using namespace std;
int d[3000][3000];
int unone;
int zero;
int one;
bool same(int a,int b,int n){                     //n*n에서 값이 다 일치하는지 확인하는 함수
    int save=d[a][b];
    for(int i=a;i<a+n;i++){
        for(int k=b;k<b+n;k++){
            if(d[i][k]!=save){
                return false;
            }
        }
    }
    return true;
}
void divide(int a ,int b ,int n){                   //분할해서 값이 같은 종이가 나올때까지 재귀함수 돌리기
    if(same(a,b,n)==true){
        if(d[a][b]==-1){
            unone++;
            return;
        }
        if(d[a][b]==0){
            zero++;
            return;
        }
        if(d[a][b]==1){
            one++;
            return;
        }
    }
    n=n/3;
    divide(a,b,n);
    divide(a,b+n,n);
    divide(a,b+2*n,n);
    divide(a+n,b,n);
    divide(a+n,b+n,n);
    divide(a+n,b+2*n,n);
    divide(a+2*n,b,n);
    divide(a+2*n,b+n,n);
    divide(a+2*n,b+2*n,n);
}
int main(){
    cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int k=1;k<=n;k++){
            cin>>d[i][k];
        }
    }
    divide(1,1,n);
    cout<<unone<<'\n';
    cout<<zero<<'\n';
    cout<<one<<'\n';
}