[백준] 1992 쿼드트리 : 실버 (java) - 분할정복

분할정복 뿌수기!!!!!!!!!!👊🏻

✔️ 문제

✔️ 풀이 코드

이 문제는 2차원 배열을 압축하는 쿼드트리(Quad Tree) 구조를 구현하는 전형적인 분할 정복 문제다.

백준 2630 색종이만들기 문제를 풀어봤다면, 쉽게 풀 수 있을 것같다. (https://cse-gr.tistory.com/178)

1. 현재 영역이 모두 같은 값(0 또는 1)이라면 → 해당 숫자 하나만 출력한다.
2. 값이 섞여 있다면 → 영역을 4등분하여 각각 재귀 호출한다.

괄호를 출력하는 코드를 어디다가 넣어야할지 고민했는데, 한 덩어리에 대한 색을 출력할 때 괄호를 출력하면 된다고 생각하니 쉽게 풀렸다. 

즉, 여는 괄호는 재귀 호출 전에, 닫는 괄호는 재귀 호출이 모두 끝난 후에 출력한다.

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

public class Main {
    static int[][] arr;         // 입력받은 영상 데이터를 저장할 2차원 배열
    static StringBuilder sb;    // 압축 결과를 저장할 문자열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());   // 영상의 크기 입력
        arr = new int[n][n];

        // 영상 데이터를 배열에 저장
        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < n; j++) {
                arr[i][j] = str.charAt(j) - '0';
            }
        }

        sb = new StringBuilder();
        cutPaper(0, 0, n);    // 전체 영상에 대해 압축 시작
        System.out.println(sb);
    }

    // 해당 영역이 모두 같은 색이면 숫자만 추가,
    // 아니라면 4등분해서 재귀적으로 압축
    public static void cutPaper(int row, int col, int size) {
        if (isSameColor(row, col, size)) {
            sb.append(arr[row][col]);  // 같은 색이면 해당 숫자만 추가
            return;
        }

        size /= 2;  // 4분할

        sb.append("(");  

        cutPaper(row, col, size);                // 왼쪽 위
        cutPaper(row, col + size, size);         // 오른쪽 위
        cutPaper(row + size, col, size);         // 왼쪽 아래
        cutPaper(row + size, col + size, size);  // 오른쪽 아래

        sb.append(")");  
    }

    // 해당 영역이 모두 같은 색(0 또는 1)인지 확인
    public static boolean isSameColor(int row, int col, int size) {
        int color = arr[row][col];
        for (int i = row; i < row + size; i++) {
            for (int j = col; j < col + size; j++) {
                if (arr[i][j] != color) return false;
            }
        }
        return true;
    }
}