[백준 1992] 쿼드트리(Java)

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

1992번: 쿼드트리

문제

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다.  N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

출력

영상을 압축한 결과를 출력한다.

풀이 설명

1. 분할 정복을 사용하여 푸는 문제이다.

2. 입력받은 영상 정보를 2차원 배열 video에 저장한다.

3. quadTree 함수에 입력받은 사이즈 N, 시작 인덱스 0,0을 넘긴다.

  3-1. 시작 인덱스들 x, y부터 체크할 마지막 인덱스 x+size, y+size까지 탐색하며, 하나라도 숫자가 다르다면 isNon에            체크하고 break

  3-2. isNon이라면, 현재 체크중인 video의 범위를 1~4사분면으로 나누어 다시 체크해야 한다.

    3-2-0. 재귀호출 전에 StringBuilder에 "("를 추가한다.

    3-2-1. 1사분면 사이즈 size/2, 시작 인덱스 x, y를 quadTree에 넘겨 재귀호출한다.

    3-2-2. 2사분면 사이즈 size/2, 시작 인덱스 x, y + size/2를 quadTree에 넘겨 재귀호출한다.

    3-2-3. 3사분면 사이즈 size/2, 시작 인덱스 x + size/2, y를 quadTree에 넘겨 재귀호출한다.

    3-2-4. 4사분면 사이즈 size/2, 시작 인덱스 x, y를 quadTree에 넘겨 재귀호출한다.

    3-2-5. 사분면의 재귀호출이 끝나면 StringBuilder에 ")"를 추가한다.

  3-3. isNon이 아니라면(숫자가 모두 같다면), StringBuilder에 그 숫자를 추가한다.

  3-4. 만약 size가 1이라면, 더이상 분할도 안되고, 숫자가 한가지밖에 없으므로 그 숫자를 StringBuilder에 추가 후                리턴한다.

Java 코드

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

public class Main {

	static int N;
	static char[][] video;
	static StringBuilder sb;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		video = new char[N][N];
		for (int i = 0; i < N; i++)
			video[i] = br.readLine().toCharArray();
		
		sb = new StringBuilder();
		quadTree(N, 0, 0);
		System.out.println(sb);
	}

	private static void quadTree(int size, int x, int y) { //size와 체크할 시작 인덱스들
		if (size == 1) {
			sb.append(video[x][y]);
			return;
		}
		
		boolean isNon = false;
		char first = video[x][y];
		flag: for(int i=x; i<x+size; i++) {
			for(int j=y; j<y+size; j++) {
				if(first != video[i][j]) {
					isNon = true; //하나라도 숫자가 다르다면
					break flag; //2중 for문 한번에 나가기
				}
			}
		}
		
		if(isNon) {
			sb.append("(");
			quadTree(size/2, x, y); //1사분면 체크
			quadTree(size/2, x, y + size/2); //2사분면
			quadTree(size/2, x + size/2, y); //3사분면
			quadTree(size/2, x + size/2, y + size/2); //4사분면
			sb.append(")");
		}
		else
			sb.append(first);
	}
}