(BOJ) 1992 풀이

#include<bits/stdc++.h>

using namespace std;
int ar[65][65];
void quad(int n,int x,int y){
    if(x==1){
        cout << ar[x][y];
        return;
    }
    int _0=0,_1=0;
    for(int i=x;i<x+n;i++){
        for(int j=y;j<y+n;j++){
            if(ar[i][j]==0)_0=1;
            else _1=1;
        }
    }
    if(!_0){
        cout << 1;
    }else if(!_1){
        cout << 0;
    }else{
        cout << "(";
        quad(n/2,x,y);
        quad(n/2,x,y+n/2);
        quad(n/2,x+n/2,y);
        quad(n/2,x+n/2,y+n/2);
        cout << ")";
    }
}
int main(void){
    ios::sync_with_stdio(0);cin.tie(0);
    int N;
    cin >> N;
    for(int i=0;i<N;i++){
        string s;
        cin >> s;
        for(int j=0;j<N;j++){
            ar[i][j]=s[j]-'0';
        }
    }
    quad(N, 0, 0);
}

함수원형

void quad(int n, int x, int y)

n : 현재 구역의 크기

x : 현재 구역의 행

y : 현재 구역의 열

 

base condition

x==1 일 때,

압축한 것과 ar[x][y] 가 똑같으니 ar[x][y] 를 출력하고 리턴.

 

재귀식

현재 구역에 0이 있는지, 1이 있는지 체크한다.

only 1, only 0, 둘 다 ← 이 3 가지 경우밖에 없으니

if 문으로 처리해주면 된다.

_0 변수가 0이라면 0이 하나도 없으니 1로 압축할 수 있으므로 1 출력

_1 변수가 0이라면 1이 하나도 없으니 0으로 압축할 수 있으므로 0 출력

 

섞인 경우

: 괄호를 출력하고, 4구역으로 나눠 재귀함수 호출한 뒤, 닫는괄호 출력

이 예제의 경우에는,

quad(4,0,0); quad(4,0,4); quad(4,4,0); quad(4,4,4);

위 4개의 함수가 호출되어 각자 자신의 영역에서 최선을 다해 압축해서 출력해줄 것이다.