백준 1992번: 쿼드트리

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

1992번: 쿼드트리

 

 문제 설명 

 

처음에 모든 영상이 0 이나 1 로 이루어져있는지 확인 -> 맞으면 0 이나 1출력 , 아니면 4등분하고 다시 0이나 1로이루어져있는지 확인 -> 반복 -> 출력.

 

 알고리즘 

 

재귀로 구현.

계속 4등분하면서 1이나 0 으로이루어져있는지 확인해가면된다 4등분 하기직전에 '('  4등분 후에 ')' <- 이것만 유의하면된다. 이거 잘못해서 오래걸렸다.

 

 코드 

 

#include<iostream>
#include<vector>
using namespace std;
 
int N;
int map[65][65];
 
vector<char> v;
void func(int n, int y, int x) {
 
    //n이 1일때 배열에 해당하는 숫자를 결과출력벡터에 push
    if (n == 1) {
        if (map[y][x])v.push_back('1');
        else v.push_back('0');
        return;
    }
 
    bool zero = true, one = true;
 
    for (int i = y; i < y + n; i++) {
        for (int j = x; j < x + n; j++) {
            if (map[i][j]==0) {
                one = false;
            }
            else {
                zero = false;
            }
        }
    }
    // 1로 압축가능
    if (one)v.push_back('1');
 
    // 0으로 압축가능
    else if (zero)v.push_back('0');
 
    // 4등분 
    else {
        v.push_back('(');
        func(n / 2, y, x);
        func(n / 2, y, x + n / 2);
        func(n / 2, y + n / 2, x);
        func(n / 2, y + n / 2, x + n / 2);
        v.push_back(')');
    }
 
}
 
int main() {
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
    func(N, 0, 0);
 
    for (int i = 0; i < v.size(); i++)cout << v[i];
}