[BOJ] 1992 쿼드트리

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

 

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

recursive

 

---------------------------------------------------풀이----------------------------------------------------

 

compress()함수에서 모든 영상이 압축될 때까지 재귀적으로 반복한다.

만약 x,y부터 시작해 n 크기의 사각형이 하나의 숫자로 이루어진 부분이라면 is_only_one()이 true일 것이고,

해당하는 숫자를 ans에 추가한다.그렇지 않으면 ans에 '('를 추가하고 네 부분으로 나누어 각각 재귀 호출한다. 마지막엔 ')'를 ans에 추가해 괄호를 닫아준다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>

using namespace std;

int map[100][100] = {0, };
string ans = "";

bool is_only_one(int x, int y, int n){
    int num = map[x][y];
    for(int i = x; i < x+n; i++){
        for(int j = y; j < y+n; j++){
            if(map[i][j] != num){
                return false;
            }
        }
    }
    return true;
}

// 맨 왼쪽 위 좌표, 크기
void compress(int x, int y, int n){
    // 0 또는 1로만 이루어져 있는 경우, ans에 그 숫자만 추가
    if(is_only_one(x, y, n)){
        ans += map[x][y]+'0';
        return;
    }
    // 네 개의 영상으로 나누기
    ans += "(";
    compress(x, y, n/2);
    compress(x, y+n/2, n/2);
    compress(x+n/2, y, n/2);
    compress(x+n/2, y+n/2, n/2);
    ans += ")";
}

int main(void){
    FASTIO;
    int N;
    cin >> N;
    char tmp;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> tmp;
            map[i][j] = tmp-'0';
        }
    }
    compress(0, 0, N);
    cout << ans << "\n";
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

이전에 풀었던 색종이를 네 부분으로 계속 자르거나 9개의 부분으로 자르는 문제의 변형이다.

재귀를 제대로 이해했는가를 보는 기본 문제.