[ 백준 1992] 쿼드트리(C++)

1992번: 쿼드트리

 

문제!

---

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다.  N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

 

---

 

 

문제 이름 그대로 쿼드트리 문제입니다!

 

간단하게 설명하면 좌표상의 0,1들을 모아놓고 현재 상태가 모두 1이라면? 1로 출력 0이라면 0으로출력

만약아니라면? >> 4등분을 해서 왼쪽위 오른쪽위 왼쪽아래, 오른쪽 아래 순서로 한번씩 다시 압축을 하러 가는 구조입니다.

 

구조에서 볼수있는것처럼 재귀! 를 통해 쉽게 해결할수있는 문제입니다.

 

 

 

 

 

 

일단 시작!

---

 

일단 필요한 변수들을 저장해줍시다. 

vector<string>map;
string answer = "";

////~~~~~





 cin.tie(0);
    ios::sync_with_stdio(0);

    string memo = "";
    int n = 0;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> memo;
        map.push_back(memo);
    }

저는 string 형으로 변수를 받아 저장했습니다.

 

 

 

 

 

다음은 현재 위치에서의 사각형 탐색(모두1인지 0인지 아닌지)를 탐색해주는 함수와 

재귀를 돌릴 함수를 하나씩 만들어 줍시다.

 

 

 

 

 

 

먼저 현재 위치에서 모두 0인지를 확인하는 함수입니다.

y,x에서 n만큼을 계속 반복해서 비교해주는 간단한 형식!

bool check(int y, int x, int n) {// 판별  위치와 몇칸볼지?
    int memo_state = map[y][x];


    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[y + i][x + j] != memo_state) {
                return false;
            }
        }
    }

    return true;

}

 

 

 

다음은 재귀를 돌릴 함수....

(, ) 괄호의 위치가 고민이였지만

void find(int y, int x, int n) {// 쪼개면서 들어가기?  시작점과 몇번째까지 볼지?

    if (n == 1) {
        answer += map[y][x];

        return;
    }


    if (check(y, x, n)) {
        answer += map[y][x];
    }
    else {
        answer += "(";

        find(y, x, n / 2);

        find(y, x + n / 2, n / 2);

        find(y + n / 2, x, n / 2);

        find(y + n / 2, x + n / 2, n / 2);

        answer += ")";


    }
}

위 처럼 사용하여 해결할수 있었습니다! 

 

 

 

굳굳

 

 

 

**ALL

#include <iostream>
#include <vector>
#include <utility>
#include <string>

#include <algorithm>
using namespace std;

vector<string>map;
string answer = "";
int check_wall = 0;



bool check(int y, int x, int n) {// 판별  위치와 몇칸볼지?
    int memo_state = map[y][x];


    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[y + i][x + j] != memo_state) {
                return false;
            }
        }
    }

    return true;

}


void find(int y, int x, int n) {// 쪼개면서 들어가기?  시작점과 몇번째까지 볼지?

    if (n == 1) {
        answer += map[y][x];

        return;
    }


    if (check(y, x, n)) {
        answer += map[y][x];
    }
    else {
        answer += "(";

        find(y, x, n / 2);

        find(y, x + n / 2, n / 2);

        find(y + n / 2, x, n / 2);

        find(y + n / 2, x + n / 2, n / 2);

        answer += ")";


    }
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    string memo = "";
    int n = 0;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> memo;
        map.push_back(memo);
    }


    find(0, 0, n);

    cout << answer << endl;
    

    return 0;
}

 

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!