[백준] 1992번 : 쿼드트리 - 자바(JAVA)

 

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

 

문제 해석

2차원 배열에 0과 1로 이루어져 있는데 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리라는 방법이 존재한다.

주어진 영상이 모두 0으로만 되어 있으면 압축결과는 "0"이 되고 모두 1로만 되어 있으면 압축결과는 "1"이 된다.

만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지 못하고 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 영상을 나누어 압축하게 됩니다. 

 

처음에 문제해석이 잘 안되었지만 전체배열을 4사분면으로 나누어 압축해야 합니다.

 

1. 우선 전체 문자열을 검사해서 압축이 되는지 확인합니다.

2. 압축이 되지 않는다면 4사분면으로 나누어 그 부분에 압축이 되는지 검사합니다.

3. 이를 반복합니다

4. 종료조건으로는 size/2 = 1이 된다면 한개는 그 자체가 전체 문자열과 동일하므로 압축됩니다.

 

코드

package day0216;

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

public class Main_1992_쿼드트리 {
	static StringBuilder sb = new StringBuilder();
	static int[][] board;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		board = new int[N][N];
		for (int i = 0; i < N; i++) {
			String temp = br.readLine();
			for (int j = 0; j < N; j++) {
				board[i][j] = temp.charAt(j) - '0';
			}
		}

		getQuadTree(0, 0, N);
		System.out.println(sb);
	}

	private static void getQuadTree(int x, int y, int size) {

		if (isCompression(x, y, size)) {
			sb.append(board[x][y]);
			return;
		}

		int newSize = size / 2;
		sb.append('(');
		// 1사분면 검사 i = 0 to N/2, j = 0 to N/2
		getQuadTree(x, y, newSize);

		// 2사분면 검사 i = 0 to N/2, j = N/2 to N
		getQuadTree(x, y + newSize, newSize);

		// 3사분면 검사 i = N/2 to N, j = 0 to N/2
		getQuadTree(x + newSize, y, newSize);

		// 4 사분면 검사 i = N/2 to N, j = N/2 to N
		getQuadTree(x + newSize, y + newSize, newSize);

		sb.append(')');
	}

	private static boolean isCompression(int x, int y, int size) {
		int value = board[x][y];

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

		return true;

	}
}