백준 1992 쿼드트리 / C++

문제 : 1992

풀이 point

분할 재귀를 활용한 문제

4분면으로 매번 분할되고 정사각형 내의 요소가 모두 1이거나 0인지 확인한다.

괄호의 위치는 재귀의 시작과 끝이다.
괄호는 재귀 시작전 한번 재귀가 완전히 끝난후 한번 오기 때문
사분면마다 괄호가 시작되고 끝난다.
-> 자세한 설명은 백준 2630 색종이 만들기 참고

풀이 순서

정사각형 내의 요소가 모두 1이거나 0인지 확인하는 함수
재귀함수

코드

//백준 1992, 쿼드트리

#include <iostream>

int N;
int grid[100][100];

std::string ans;

bool check(int n, int x, int y){
    int init = grid[x][y];
    for(int i{x}; i<x+n; ++i){
        for(int j{y}; j<y+n; ++j){
            if(grid[i][j] != init) return false;
        }
    }
    return true;
}

void recur(int n, int x, int y){
    if(check(n, x, y)){
        if(grid[x][y] == 1) ans.push_back('1');
        else ans.push_back('0');
    }
    else{
        int half = n/2;
        ans.push_back('(');
        recur(half, x, y);
        recur(half, x, y+half);
        recur(half, x+half, y);
        recur(half, x+half, y+half);
        ans.push_back(')');
    }
}

int main(){
    
    std::cin >> N;

    for(int i{0}; i<N; ++i){
        std::string row;
            std::cin >> row;
        for(int j{0}; j<N; ++j){
            grid[i][j] = row[j]-'0';
        }
    }

    recur(N, 0, 0);
    std::cout << ans;


    return 0;
}