BOJ01992 쿼드트리

https://www.acmicpc.net/problem/1992 (opens new window)

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

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

quadTree

4방향으로 영역을 나눠 탐색을 진행한다.

모든 value가 같은 경우 압축 가능하다고 판단한다. 압축이 가능할 경우 괄호에 숫자를 채워간다.

private static void quadTree(int row, int col, int size) {

    // 압축 가능한 경우 하나의 색으로 압축
    if (isSameColor(row, col, size)) {
        stringBuilder.append(image[row][col]);
        return;
    }

    int newSize = size / 2;

    stringBuilder.append("(");

    quadTree(row, col, newSize);
    quadTree(row, col + newSize, newSize);
    quadTree(row + newSize, col, newSize);
    quadTree(row + newSize, col + newSize, newSize);

    stringBuilder.append(")");
}

private static boolean isSameColor(int row, int col, int size) {
    int value = image[row][col];

    for (int i = row; i < row + size; i++) {
        for (int j = col; j < col + size; j++) {
            if (image[i][j] != value) {
                return false;
            }
        }
    }

    return true;
}

제출 코드

아래는 최종 제출 코드이다.

import java.util.Scanner;

public class BOJ1992 {

    private static int n;
    private static int[][] image;
    private static StringBuilder stringBuilder = new StringBuilder();

    private static void quadTree(int row, int col, int size) {

        // 압축 가능한 경우 하나의 색으로 압축
        if (isSameColor(row, col, size)) {
            stringBuilder.append(image[row][col]);
            return;
        }

        int newSize = size / 2;

        stringBuilder.append("(");

        quadTree(row, col, newSize);
        quadTree(row, col + newSize, newSize);
        quadTree(row + newSize, col, newSize);
        quadTree(row + newSize, col + newSize, newSize);

        stringBuilder.append(")");
    }

    private static boolean isSameColor(int row, int col, int size) {
        int value = image[row][col];

        for (int i = row; i < row + size; i++) {
            for (int j = col; j < col + size; j++) {
                if (image[i][j] != value) {
                    return false;
                }
            }
        }

        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        image = new int[n][n];

        for (int i = 0; i < n; i++) {
            String string = scanner.next();
            for (int j = 0; j < n; j++) {
                image[i][j] = string.charAt(j) - '0';
            }
        }

        quadTree(0, 0, n);

        System.out.println(stringBuilder);
    }
}

#BOJ #분할 정복 #재귀