백준 #1992 쿼드트리

 

백준 1992번 쿼드 트리 문제이다.

 

그래프를 활용한 문제로, 재귀를 이용하면 해결할 수 있는 문제이다.

 

처음 문제를 보면 문제가 잘 이해가 가지 않는데,

 

위에 그림으로 준 예시와, 예제를 잘 들여다 보면 쉽게 파악할 수 있다.

 

정사각형을 한 뭉텅이로 보고 문제 해결을 시도하면 된다.

 

첫 번째 입력에서 전체 행의 개수를 주기 때문에, 

행의 개수를 점차 적으로 줄여나가면서 문제를 해결할 수 있다.

 

#include <iostream>
#include <string>
using namespace std;
int n;
string s;
char a[101][101];
string quard(int y, int x, int size ){
    if(size == 1) return string(1,a[y][x]);
    char b = a[y][x];
    string ret = "";
    for(int i = y; i < y + size; i++) {
        for(int j = x; j < x + size; j++) {
            if(b != a[i][j]) {
                ret += '(';
                ret += quard(y,x, size / 2);
                ret += quard(y, x + size / 2 , size / 2);
                ret += quard(y + size/ 2, x, size / 2);
                ret += quard(y + size/ 2, x + size/2, size / 2);
                ret += ')';
                return ret;
            }
        }
    }
    return string(1, a[y][x]);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> s;
        for(int j = 0; j < n; j++) {
            a[i][j] = s[j];
        }
    }
    cout << quard(0,0,n) << '\n';
    return 0;
}