Taxol

I’ve always been.

백준 1992 - 쿼드트리

Updated:

Java

1992 번 - 쿼드트리

문제

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

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

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

접근 방법

분할 정복 문제이다. 3가지

  1. 먼저 2n x 2n배열이 0 또는 1로만 이루어져 있는지 확인한다. 같은 정보로 이루어져 있으면, 해당하는 정보를 출력하고 종료한다.
  2. 만약 정보가 섞여있다면, 2n x 2n 크기의 배열을 4개의 2n-1 x 2n-1배열로 나누어 다시 탐색한다.
  3. 배열의 크기가 1x1까지 줄어들면, 그 정보를 출력하고 종료한다.

구현

(배열의 크기, 시작점 y, 시작점 x)를 매개변수로 주어지는 재귀함수를 통해 구현하였다.
시작점과 배열의 크기만큼 데이터를 확인하여, 다 동일하면 그 값을 StringBuilder에 저장한다.
만약 0과 1이 섞여있다면 4등분으로 세분화 해야 하므로, ‘(‘를 StringBuilder에 저장하고 배열을 4등분 하여 그 시작점과 n/2의 크기를 매개변수로 함수를 호출한다.
4개의 함수를 탐색이 끝나면 ‘)’로 닫아준다.

코드

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

public class Main {
	static int arr[][];
	static StringBuilder sb;
    public static void main(String []args) throws IOException {        
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
    	int n = stoi(br.readLine());
    	arr = new int[n][n];
    	String temp;
    	for(int i = 0; i < n; i++) {
    		temp = br.readLine();
    		for(int j = 0; j < n; j++) {
    			arr[i][j] = temp.charAt(j) - '0';
    		}
    	}
    	sb = new StringBuilder();	// 출력 값을 담을 StringBuilder
    	quardTree(n,0,0);
    	System.out.println(sb.toString());
    	br.close();
    }
    
    static void quardTree(int size, int y, int x) {
		// 배열의 크기가 1x1까지 줄어들면, 정보를 출력하고 종료
    	if(size == 1) {
    		sb.append(arr[y][x]);
    		return;
    	}
		// 현재 크기의 배열에서 기준이 되는 정보, standard
    	int strdD = arr[y][x];
    	boolean isSame = true;
    	end : for(int i = y; i < size + y; i++) {
    		for(int j = x; j < size + x; j++) {
    			if(arr[i][j] != strdD) {		// 정보가 섞여있다면
    				isSame = false;
    				break end;
    			}
    		}
    	}
    	
    	if(isSame) {		// 배열의 값이 전부 0 혹은 1로 이루어져 있다면
    		sb.append(strdD);	// 정보를 출력한다.  
    	}
    	else {	// 4 등분으로 나누어 재탐색 한다.
    		sb.append('(');
    		quardTree(size / 2, y, x);
    		quardTree(size / 2, y, x + size / 2);
    		quardTree(size / 2, y + size / 2, x);
    		quardTree(size / 2, y + size / 2, x + size / 2);
    		sb.append(')');
    	}
    	
    }
    
    static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐⭐★★★

후기

운 좋게 한번에 생각한대로 구현하였더니 풀렸던 문제
StringBuilder를 처음으로 제대로 사용한 것 같다.

개선할 점

없

You may also enjoy