[알고리즘] 1992번: 쿼드트리

0. 문제

 

1992번: 쿼드트리

 

---

1. 문제 이해

 

• 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축.
• (0(0011)(0(0111)01)1)

 

왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 모두가 같은 값이 될 때까지 4등분 한다.

→ 재귀적으로 호출한다.

 

---

2. 제출

 

// 백준 1992번 퀴드트리
#include <iostream>
#include <string>

using namespace std;

const int max_n = 64;
const int dy[] = {0, 0, 1, 1};
const int dx[] = {0, 1, 0, 1};
int n, a[max_n][max_n];
string s, ret="";

string quadtree(int y, int x, int n){
    string str = "";
    bool pass = true;
    int tmp = a[y][x];

    for(int i=y; i<y+n; i++)
        for(int j=x; j<x+n; j++)
            if(a[i][j] != tmp)
                pass = false;

    if(pass){
        str += to_string(tmp); 
    }else{
        str += "(";
        for(int i=0; i<4; i++){
            int ny = y+dy[i]*n/2;
            int nx = x+dx[i]*n/2;
            str +=    quadtree( ny, nx, n/2);
        }
        str += ")";
    }

    return str;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin  >> n;

    for(int i = 0; i < n; i++){
        cin >> s;
        for(int j = 0; j < n; j++){
            a[i][j] = s[j] - '0';
        }
    }

    ret = quadtree(0,0, n);

    cout << ret << "\n";

    return 0;
}

• quadtree를 재귀적으로 호출.

 

string quadtree(int y, int x, int n){
    string str = "";
    bool pass = true;
    int tmp = a[y][x];

    for(int i=y; i<y+n; i++)
        for(int j=x; j<x+n; j++)
            if(a[i][j] != tmp)
                pass = false;

    if(pass){
        str += to_string(tmp); 
    }else{
        str += "(";
        for(int i=0; i<4; i++){
            int ny = y+dy[i]*n/2;
            int nx = x+dx[i]*n/2;
            str +=    quadtree( ny, nx, n/2);
        }
        str += ")";
    }

    return str;
}

• 범위 n*n 내에 모든 값이 동일하면 그 값을 반환.
• 그렇지 않으면 괄호 안에 범위를 4 등분해서 quadtree를 재귀적으로 호출.

 

가. 개선점

int n, a[max_n][max_n];
...
string quadtree(int y, int x, int n){

• 전역변수 n과 매개변수 n의 변수명이 동일해서 잘못 이해할 수 있다. 매개변수 n보다는 size로 교환할 것을 추천.

 

int tmp = a[y][x];
...
if(a[i][j] != tmp)

• tmp보다는 flag를 추천.

 

---

나. 분할 정복 알고리즘

 

위와 같은 것을 Divide & Conquer라고 한다.

 

분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다.

 

• 분할 정복 알고리즘은 보통 재귀 함수(recursive function)를 통해 자연스럽게 구현된다.
• 빠른 실행이나 부문제 해결 순서 선택을 위해, 재귀호출을 사용하지 않고 스택, 큐(queue) 등의 자료구조를 이용하여 분할 정복법을 구현하는 것도 가능하다.

 

아래는 stack을 이용해서 분할 정복 알고리즘을 구현한 예시다.

[알고리즘] 3986번: 좋은 단어

 

출처 : https://ko.wikipedia.org/wiki/분할_정복_알고리즘

---