백준 - 1992 : 쿼드 트리 [자바]

구글링 참고해서 풀었습니다...
다시 폴어볼 것‼️

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

public class Main {
	// 쿼드트리(Quad Tree) : 흑백 영상을 압축하여 표현하는 데이터 구조
	// 0 : 흰 점, 1 : 검은 점
	// 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축
	// 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 0
	// 주어진 영상이 모두 1로만 되어 있으면 압축 결과는 1
	// 0, 1이 섞여 있으면, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 4개의 영상으로 나누어서 압축

	static int[][] video;
	static StringBuilder sb = new StringBuilder();;

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

		int N = Integer.parseInt(br.readLine()); // 영상의 크기 N
		// 2의 제곱 수, 1<= N <= 64

		video = new int[N][N];
		for (int i = 0; i < N; i++) {
			String str = br.readLine();

			for (int j = 0; j < N; j++) {
				video[i][j] = str.charAt(j) - '0';
			}

		}
		quadTree(0, 0, N);
		System.out.println(sb);
		br.close();

	}

	static void quadTree(int r, int c, int N) {
		if (check(r, c, N)) { // 압축 가능하면 압축
			sb.append(video[r][c]);
			return;
		}

		// 압축 불가능하면 요렇게
		int size = N / 2;
		sb.append("(");

		quadTree(r, c, size); // 왼쪽 위
		quadTree(r, c + size, size); // 오른쪽 위
		quadTree(r + size, c, size); // 왼쪽 아래
		quadTree(r + size, c + size, size); // 오른쪽 아래

		sb.append(")");

	}

	// 분할한 거 안에 다 같으면 true 리턴
	// 다른 거 포함되어있으면 false 리턴
	static boolean check(int r, int c, int N) {
		int value = video[r][c];

		for (int i = r; i < r + N; i++) {
			for (int j = c; j < c + N; j++) {
				if (video[i][j] != value) {
					return false;
				}
			}
		}
		return true;
	}
}

좋은 웹페이지 즐겨찾기