[재귀 / BOJ 1992 / C++] 쿼드트리

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

1992번: 쿼드트리

1) 재귀함수 q(x, y, n)를 설정한다.
 - 종료조건 : n==1 이 되면 x,y에 해당하는 숫자를 push_back 해준다.
 - 반복 : x, y부터 x+n,y+n까지 탐색을 시작한다. 만약 x,y에 해당하는 숫자와 다른 숫자가 나온다면,  q를 호출하여
            4번을 재귀적으로 돌린다. 추가로, 여는 괄호 '(' 를 push_back 해준다.
            4번의 재귀가 끝난다면, 닫는 괄호 ')' 를 push_back 해준다.
2) vector를 출력해준다.

우선, 무조건 4등분을 한다는 생각을 깔아두자!

 

단순히 생각하면 [0][0]부터 계속 탐색하다가 [0][0]과 다른 것이 나오면 같이 묶을 수 없기 때문에

4등분을해서 등분한 각각을 다시 탐색해나가야한다.

 

이때, N/2 * N/2 정사각형 4개가 나온다.

 

따라서 각각의 정사각형에 대해 탐색한다.  만약  N/2 * N/2 사각형 내부에 다른 것이 하나가 존재한다면, 그 정사각형을 다시 4등분을 해야한다. 그러면 다시 N/8 * N/8 사각형 4개가 나온다. 

이런식으로 보다보면 결국 재귀적으로 문제를 풀어야 할것이라 감이 올 것이다!!

 

#include <bits/stdc++.h>

using namespace std;

int N;
char board[65][65];
string s;

vector<char> a;

void q(int x, int y, int n){
    if(n==1) {a.push_back(board[x][y]); return;}
    
    char chk = board[x][y];
    for(int i = x ; i < x+n ; i++){
        for(int j = y ; j < y+n ; j++){
            if(chk!=board[i][j]) {
                a.push_back('(');
                
                q(x, y, n/2);
                
                q(x, y+n/2, n/2);
                q(x+n/2, y, n/2);
                q(x+n/2, y+n/2, n/2);
                
                a.push_back(')');
                return;
            }
        }
    }
    
    a.push_back(chk);
    
    
    
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    
    
    for(int i = 0 ; i < N ; i++){
        cin >> s;
        
        for(int j = 0 ; j < N ; j++){
            board[i][j] = s[j];
        }
    }
    
    q(0,0,N);
    
    for(auto i : a) cout << i;
    
}