백준 1992: 쿼드트리

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

1992번: 쿼드트리

 

 

이 문제는 일단 분할 정복으로 접근했다 .

사실 종이의 개수 1780번 문제와 거의 흡사한 문제이며  이건 재귀적으로 풀면 된다.

일단 4등분해야하기 때문에 왼쪽 위 오른쪽 위 왼쪽 아래 오른쪽 아래 순으로 재귀를 계속해주면 되고

n등분한 구역에서 모든 값이 일치할때 마다 탈출해주면 된다.

코드를 보고 이해하자 (여기서 나는 메모리 효율을 위해 벡터를 이용했다)

#include <iostream>
#include <vector>
#include <string>
using namespace std;
bool same(vector<vector<int>>& v,int a,int b, int n){         //n*n 범위에서 값이 다 일치 하는지
    for(int i=a;i<a+n;i++){
        for(int k=b;k<b+n;k++){
            if(v[i][k]!=v[a][b]){
                return false;
            }
        }
    }
    return true;
}
void divide(vector<vector<int>>& v,int a, int b, int n){          ////4분할하는 함수
    if(same(v,a,b,n)==true){               //값이 일치하면 그 값 하나 출력 그리고 탈출
        cout << v[a][b];
    }else{           
        cout <<'(';                         //값이 일치하지 않으면 4등분 왼쪽 위. 오른쪽 위 . 왼쪽 아래, 오른쪽 아래 순으로 출력
        n=n/2;
        for(int i=0;i<2;i++){
            for(int k=0;k<2;k++){
                divide(v,a+i*n,b+k*n,n);
            }
        }
        cout<<')';
    }
}
int main(){
    cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    vector<vector<int>> v(n);
    for(int i=0;i<n;i++){
        string s;
        cin >>s;
        for(int k=0;k<n;k++){
            v[i].push_back(s[k]-'0');
        }
    }
    divide(v,0,0,n);
}