문제 출처

https://www.acmicpc.net/problem/1992
단계별로 풀어보기 > 분할 탐색 > 쿼드트리

문제 설명

주어진 영상이 모두 0으로만 되어 있을 때 "0", 모두 1로만 되어있을 때 "1"로 출력된다.
왼쪽 위, 오른ㅓ쪽 위, 왼쪽 아래, 오른쪽 아래에 해당하는 영상 4개를 나누어압축할 때, 압축한 결과를 출력하는 프로그램을 작성하라.

접근 방법

영상의 한 범위 전체가 동일한 색으로 되어있는지 가장 먼저 판별한다. 만약 같다면 해당 숫자에 대해서 결과를 저장하고, 다르다면 범위의 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래에 해당하는 범위를 다시 재귀를 이용하여 검증하는 방식을 이용한다. 단, 이때 재귀를 시작하기 전 결과에 먼저 "("를 저장하고, 각 범위 재귀가 다 끝나면 ")"을 저장한다.

import java.io.*;
import java.util.StringTokenizer;

public class 쿼드트리 {
    public static int[][] arr;
    public static StringBuilder sb;

    public static boolean isPossible(int x, int y, int size){
        int value = arr[x][y];

        for(int i = x; i < x + size; i++){
            for(int j = y; j < y + size; j++){
                if(value != arr[i][j]){
                    return false;
                }
            }
        }
        return true;
    }

    public static void quadTree(int startx, int starty, int size){

        if(isPossible(startx, starty, size)) {
            sb.append(arr[startx][starty]);
            return;
        }

        sb.append("(");

        int nextSize = size / 2;

        quadTree(startx, starty, nextSize);
        quadTree(startx, starty + nextSize, nextSize);
        quadTree(startx + nextSize, starty, nextSize);
        quadTree(startx + nextSize, starty + nextSize, nextSize);

        sb.append(")");
    }

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

        int N = Integer.parseInt(br.readLine());

        arr = new int[N][N];
        sb = new StringBuilder();

        for(int i = 0; i < N; i++){
            String st = br.readLine();
            for(int j = 0; j < N; j++){
                arr[i][j] = st.charAt(j) - '0';
            }
        }
        quadTree(0,0,N);

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();

    }
}

알게된 점

추상화하지 않고, quadTree에 4개의 범위를 검증하는 로직을 짰었는데, 그 과정에서 전체 범위가 동일할 경우를 고려하지 않고 "(",")"를 저장하는 로직을 짰었다.

정답 코드의 시간 복잡도는, 처음 isPossible이 O(N^2)이고, 그리고 만약에 안에서 재귀가 발생하게 된다면 N/2가 계속 발생하게 되니까 O(N^2logN)이 된다.

문제푼 흔적