[백준] 1992번 - 쿼드트리 (Silver 1)

문제 링크

백준 1992번 - 쿼드트리 (Silver 1)

문제 설명

주어진 영상을 쿼드 트리로 압축한다.
쿼드 트리는 주어진 원소가 모두 0이면 0 1개로, 1이면 1 1개로 압축한다.
둘 다 아닌 경우에는 전체를 4개의 영역 a1, a2, a3, a4로 쪼개서 (a1압축 a2압축 a3압축 a4압축)로 표기한다.

정답 코드 및 설명

전형적인 분할 정복 문제로, 전체를 계속 4개의 영역으로 쪼갰다가 합치면 된다.
4개의 영역으로 쪼개는데에는 Arrays.copyOfRange 메소드를 사용하였다.
이 메소드는 배열을 입력받은 범위만큼 복사해준다.

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

public class Main {

    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());
        int video[][] = new int[N][N];
        String str;
        for (int i = 0; i < N; i++) {
            str = br.readLine();
            for (int j = 0; j < N; j++) {
                video[i][j] = str.charAt(j) - '0';
            }
        }
        bw.write(zip(video) + "\n");
        bw.close();
    }

    static String zip(int video[][]) {
        StringBuilder sb = new StringBuilder();
        int N = video.length;

        // 모두가 0이거나 1인 경우
        // 원소의 개수가 0, 1, 2처럼 3가지 이상이면 이 풀이는 사용할 수 없다(ex. 백준 1780번)
        if (sum(video) % (N * N) == 0) {
            sb.append(sum(video) / (N * N));
            return sb.toString();
        }

        // 영상 네개로 쪼개기
        else {
            int split00[][] = new int[N / 2][N / 2];
            int split01[][] = new int[N / 2][N / 2];
            int split10[][] = new int[N / 2][N / 2];
            int split11[][] = new int[N / 2][N / 2];
            for (int i = 0; i < N / 2; i++) {
                split00[i] = Arrays.copyOfRange(video[i], 0, N / 2);
                split01[i] = Arrays.copyOfRange(video[i], N / 2, N);
                split10[i] = Arrays.copyOfRange(video[i + N / 2], 0, N / 2);
                split11[i] = Arrays.copyOfRange(video[i + N / 2], N / 2, N);
            }
            sb.append('(');
            sb.append(zip(split00));
            sb.append(zip(split01));
            sb.append(zip(split10));
            sb.append(zip(split11));
            sb.append(')');
        }
        return sb.toString();
    }

    static int sum(int video[][]) {
        int N = video.length;
        int sum = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                sum += video[i][j];
        }
        return sum;
    }
}