[백준 1992번] [분할 정복/ 재귀] 쿼드트리

백준 14601번 샤워실 바닥 깔기 문제와 비슷한 느낌으로 처리하면 된다.

viyoung.tistory.com/146

[백준 14601번] [분할 정복] 샤워실 바닥 깔기 (Large)

위의 문제와 14601번 문제의 공통점은 4개의 영역으로 나눠서 분할정복 한 뒤, 각각의 정보를 통해 전체 영역의 정보를 처리하는 것이다.

이 문제의 경우 안에 있는 element결과를 이용해서 바깥 부분에 괄호를 감싸야하므로

(좌상단정보 + 우상단 정보 + 좌하단정보 + 우하단정보)이런식으로 재귀적으로 감싸야 한다.

 

이를 해결하기 위해서는 재귀와 분할정복을 활용해주면 된다.

예상한 것처럼 Recursion의 Basecase는 size가 1이다. 즉, 이 부분에서 size가 function의 argument로 있어야 함을 추론할 수 있고 size가 1인 데이터를 확인해야하는 작업을 거쳐야하므로 x, y도 argument로 있어야함을 추론할 수 있다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
int n;
vector<string> data_value;

string checker(int size, int x, int y){
    if(size == 1){
        if(data_value[x][y] == '0') return "0"; // white
        else return "1"; // black
    }
    else{
        string left_up = checker(size / 2, x, y);
        string right_up = checker(size / 2, x, y + (size / 2));
        string left_down = checker(size / 2, x + (size / 2), y); 
        string right_down = checker(size / 2, x + (size / 2), y + (size / 2));

        if(left_up == left_down && right_up == right_down && left_up == right_up){
            if(left_up == "0"){
                return "0";
            }
            else if(left_up == "1"){
                return "1";
            }
        }
        return "(" + left_up + right_up + left_down + right_down + ")";
    }
}

int main(void){
    fastio;
    cin >> n;

    for(int i = 0; i < n; i++){
        string temp;
        cin >> temp;
        data_value.push_back(temp);   
    }

    cout << checker(n, 0, 0) << "\n";
    return 0;
}