백준 - 1992번(쿼드트리)

문제 출처: https://www.acmicpc.net/problem/1992

문제

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

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

• 위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다. N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        char[][] matrix = new char[N][N];

        for (int i = 0; i < N; i++) {
            matrix[i] = reader.readLine().toCharArray();
        }

        recursive(matrix, N, 0, 0);

        System.out.println(sb);
    }

    private static void recursive(char[][] matrix, int N, int startRow, int startCol) {
        if (N == 1) {
            sb.append(matrix[startRow][startCol]);
            return;
        }

        char check = matrix[startRow][startCol];
        boolean flag = true;

        Outer: for (int i = startRow; i < N + startRow; i++) {
            for (int j = startCol; j < N + startCol; j++) {
                if (matrix[i][j] != check) {
                    flag = false; // 통합 불가
                    break Outer;
                }
            }
        }

        if (flag) {
            sb.append(check);
            return;
        }

        sb.append("(");
        recursive(matrix, N / 2, startRow, startCol);
        recursive(matrix, N / 2, startRow, startCol + N / 2);
        recursive(matrix, N / 2, startRow + N / 2, startCol);
        recursive(matrix, N / 2, startRow + N / 2, startCol + N / 2);
        sb.append(")");
    }

}

• 기본적인 풀이의 접근 방식은 1074번(Z)와 같다. 사각형을 4사분면으로 나누어 조건을 충족할 때까지 재귀를 반복하여 모든 부분을 처리한다. 각 좌표의 첫 값을 char 배열에 저장해두고, 반복문을 수행하면서 하나라도 다른 원소가 존재할 경우 boolean flag를 통해 반복을 종료하고 다시 사각형을 나누는 작업을 진행하도록 하였다. 모든 원소가 같을 경우 해당 사각형의 원소들을 하나로 합치고 StringBuilder에 저장한 후 종료한다.