백준 1992번 쿼드트리

BOJ boj 백준 1992번 쿼드트리 

#include<iostream>

#include<string>

#include<vector>

#include<random>

#include<cstring>

#include<queue>

#include<functional>

#include<algorithm>

using namespace std;

 

 

int N;

vector<string> arr;

string decompress(int y,int x,int size) {

    char head = arr[y][x];

    bool check = true;

    //범위내 모든 글자 일치하는지 확인, 

    for (int dy = y; dy < y+size; ++dy) {

        for (int dx = x; dx < x+size; ++dx) {

                //불일치하면 네 부분으로 분할

                if (head != arr[dy][dx]) {

                check = false;

                break;

            }

        }

        if (!check)

            break;

    }

    if (check) {

        //범위내 모든 글자가 일치하면 일치한 문자 출력

        return string(1,head);

    }

    else {

        //네 부분을 각각 순서대로 압축 해제한다.

        int half = size / 2;

        string upperLeft=decompress(y, x, half);

        string upperRight=decompress(y, x + half, half);

        string lowerLeft=decompress(y+half, x, half);

        string lowerRight=decompress(y+half, x + half, half);

        return string("(") + upperLeft + upperRight + lowerLeft + lowerRight+string(")");

    }

}

 

int main(void) {

    cin >> N;

    arr = vector<string>(N);

    for (int i = 0; i < N; i++)

        cin >> arr[i];

    string resolve = decompress(0, 0, N);

    cout << resolve << endl;

 

    return 0;

}

Colored by Color Scripter

cs

문제 출처:https://www.acmicpc.net/problem/1992

문제를 푸는 방법은 쿼드 트리 압축 해제하는 것입니다.

네가지 영역을 분할 하는 방법이 생소해서 어려워 보이지만  방법만 알면 쉬운문제였습니다.