[JAVA]1992 쿼드트리, 분할 정복

 📚 문제  

1992번: 쿼드트리

 

🔍 아이디어  

사각형을 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래로 묶은 후에 해당 영역이 모두 같은 색으로 칠해져있다면 숫자를 입력하고 칠해져 있지 않다면 다시 한분 4등분 분할하여 한영역이 모두 같은 색이 될때까지 진행하며 영역의 값을 구해나간다.

예제 입력

8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

예제 출력

((110(0101))(0010)1(0001))

📝 풀이 

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

public class Main {
    private char[][] image;
    private StringBuilder quadTreeBuilder;

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        image = new char[n][];

        for (int i = 0; i < n; i++) {
            image[i] = br.readLine().toCharArray();
        }
        quadTreeBuilder = new StringBuilder();
        compressQuad(n, 0, 0);
        System.out.println(quadTreeBuilder);
    }

    private void compressQuad(
            //n : 정사각형 한변의 길이
            int n,
            //x: 정사각형의 시작 x index
            int x,
            //y: 정사각형의 시작 y index
            int y) {

        //현재 사각형이 모두 같은 색으로 칠해져 있다면
        if (isSuccess(n, x, y)) {
            quadTreeBuilder.append(image[x][y]);
        } else {
            //4등분하여 재귀호출한다.
            quadTreeBuilder.append("(");

            int half = n / 2;
            compressQuad(half, x, y); //왼쪽 상단
            compressQuad(half, x, y + half);//오른쪽 상단
            compressQuad(half, x + half, y); //왼쪽 하단
            compressQuad(half, x + half, y + half); //오른쪽 하단.

            quadTreeBuilder.append(")");
        }
    }

    //조건을 만족하는지 확인하는 메소드
    private boolean isSuccess(int n, int x, int y) {
        char init = image[x][y];
        for (int i = x; i < x + n; i++) {
            for (int j = y; j < y + n; j++) {
                if (image[i][j] != init) return false;
            }
        }
        return true;
    }
}