백준 1992번 쿼드트리

문제 링크입니다: https://www.acmicpc.net/problem/1992

재밌는 분할정복 문제였습니다.

Algospot의 QUADTREE 문제와 제목은 같지만 유형이 좀 다른 문제였습니다.

알고리즘은 아래와 같습니다.

1. 현재 구간에 있는 숫자들이 0으로만 이루어지거나 1로만 이루어져있다면 해당 숫자를 출력합니다.

2. 1번 조건이 성립하지 않을 경우 '('를 출력하고 2사분면, 1사분면, 3사분면, 4사분면 순서로 구간을 절반으로 잘라 재귀호출하고 ')'를 출력합니다.

3. 기저 사례는 구간의 크기가 1일 경우이고 구간의 크기가 1이면 해당 숫자를 출력합니다.

#include <iostream>

#include <string>

using namespace std;

 

const int MAX = 64;

 

int N;

int arr[MAX][MAX];

 

void compress(int n, int y, int x)

{

        //기저 사례

        if (n == 1)

        {

                 cout << arr[y][x];

                 return;

        }

 

        bool zero = true, one = true;

        for (int i = y; i < y + n; i++)

                 for (int j = x; j < x + n; j++)

                         if (arr[i][j])

                                 zero = false;

                         else

                                 one = false;

 

        if (zero)

                 cout << 0;

        else if(one)

                 cout << 1;

        else

        {

                 cout << "(";

                 compress(n / 2, y, x); //2사분면

                 compress(n / 2, y, x + n / 2); //1사분면

                 compress(n / 2, y + n / 2, x); //3사분면

                 compress(n / 2, y + n / 2, x + n / 2); //4사분면

                 cout << ")";

        }

        return;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N;

 

        bool zero = true, one = true;

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

        {

                 string s;

                 cin >> s;

 

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

                         arr[i][j] = s[j] - '0';

        }

 

        compress(N, 0, 0);

        cout << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~