쿼드트리 (boj 1992)

쿼드트리 문제는 Divide and conquer 를 활용하는 전형적인 문제입니다.

 

저의 경우에는 최초로 주어진 N을 size 로 두고, 반복문을 쭉 돌면서 다른 숫자가 있는지 찾아봅니다.

만약 다른 숫자가 발견되지 않고 모든 숫자가 같은 숫자라면 그 숫자로 압축이 가능합니다. (Best 케이스)

만약 다른 숫자가 발견된다면 이는 4등분해야하는 상황인 것이죠. 그렇다면 이들을 4등분한 지점을 left, top 으로 주고, size 를 절반으로 나눕니다.

그리고 위에서 했던 과정을 반복합니다.

 

코드

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>

#define INF 987654321

int N;
char map[70][70];

void DFS(int left, int top, int size) {
    char c = map[top][left];

    if (size == 1) {
        putchar(c);
        return;
    }

    for (int y = 0; y < size; y++) {
        for (int x = 0; x < size; x++) {
            if (c != map[top + y][left + x]) {
                printf("(");
                DFS(left, top, size / 2);
                DFS(left + size / 2, top, size / 2);
                DFS(left, top + size / 2, size / 2);
                DFS(left + size / 2, top + size / 2, size / 2);
                printf(")");
                return;
            }
        }
    }

    putchar(c);
}

int main() {
    scanf("%d", &N);
    for (int n = 0; n < N; n++) {
        scanf("%s", map[n]);
    }

    DFS(0, 0, N);

    return 0;
}

 

코드1이 반복문을 돌아보고 재귀함수 호출을 했습니다. 이 방법은 직관적이긴하지만 최악의 경우에는 반복문은 반복문대로 다 돌면서 재귀 호출은 재귀호출대로 하는 단점이 있습니다.

생각나는 단점은 각 정사각형마다 맨 오른쪽 맨 끝 부분에 1이 몇개씩 들어있다거나.. 하는 경우가 되겠네요

 

그래서 그냥 재귀를 돌면서 정사각형으로 묶어내는 방식이 있습니다.

DFS()가 호출되면 사분할하여 DFS() 를 재귀호출합니다. 이 DFS() 는 자기 자신의 영역 안에 숫자들이 어떤 구성을 갖고 있는지를 리턴합니다. 그와 동시에 해당 숫자들을 Stack 에 넣습니다.

'0'으로 만 이루어져있거나 '1'로만 이루어져있으면 '0', '1'을 각각 리턴하고, 이 둘이 섞여있으면 0을 리턴합니다.

그리고 사분할하여 호출한 내부 DFS() 들이 모두 같은 숫자로 이루어져있으면 Stack 에서 모두 빼내고, '0', '1'을 하나만 딱 넣어주는거죠

만약 모두 같은 숫자로 이루어져 있지 않다면 스택에서 빼내지 않습니다.

코드2

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>

#define INF 987654321

int N;
char map[70][70];
std::stack<char> stack;

char DFS(int left, int top, int size) {
    char c = map[top][left];
    char buf[4];

    if (size == 1) {
        stack.push(c);
        return c;
    }

    stack.push(')');

    int half = size / 2;
    buf[3] = DFS(left + half, top + half, half);
    buf[2] = DFS(left, top + half, half);
    buf[1] = DFS(left + half, top, half);
    buf[0] = DFS(left, top, half);

    if (buf[0] != 0 && buf[0] == buf[1] && buf[0] == buf[2] && buf[0] == buf[3]) {
        for (int i = 0; i < 5; i++)
            stack.pop();

        stack.push(buf[0]);
        return buf[0];
    }

    stack.push('(');
    return 0;
}

int main() {
    scanf("%d", &N);
    for (int n = 0; n < N; n++) {
        scanf("%s", map[n]);
    }

    DFS(0, 0, N);

    while (!stack.empty()) {
        char c = stack.top();
        stack.pop();

        putchar(c);
    }
    return 0;
}