[백준] 1922 쿼드트리

문제

---

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

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

 

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

 

 

 

풀이

---

4등분으로 나눠 가며 해당 배열이 한가지 숫자로 채워진 상태면 그 숫자를 리턴하고 아니라면 다시 재귀를 분할하여 재귀를 하는 방식으로 단순히 구현해주면 되는 문제다.

 

static void solution(int startR, int startC, int endR, int endC) {

	int result = canPress(startR, startC, endR, endC);
	if(result != -1) {
		sb.append(result);
		return;
	}
	
	sb.append("(");
	int divR = (endR - startR) / 2;
	int divC = (endC - startC) / 2;
	
	solution(startR, startC, startR + divR, startC + divC);
	solution(startR, startC + divC, startR + divR, endC);
	solution(startR + divR, startC, endR, startC + divC);
	solution(startR + divR, startC + divC, endR, endC);		
	sb.append(")");
	
}

위의 코드가 핵심코드다. 현재의 4등분한 배열을 확인하고 압축할 수 있는 상태가 아니라면 다시 4등분하여 재귀하여 주는 방식이다.

 

이때 괄호는 재귀를 들어갈때 넣어주면 된다.

 

 

<전체코드>

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

public class Main {	

	static StringBuilder sb = new StringBuilder();
	static int[][] board;
		
	static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		int n = parseInt(bufferedReader.readLine());
		board = new int[n][n];
		
		for(int i = 0 ; i < n ; i++) {
			String[] st = bufferedReader.readLine().split("");
			
			for(int j = 0 ; j < n ; j++) {
				board[i][j] = parseInt(st[j]);
			}
		}
		
		solution(0,0, n,n);
		System.out.println(sb);
	}
	
	static int canPress(int startR, int startC, int endR, int endC) {
		
		int tmp = board[startR][startC]; 
		for(int i = startR; i < endR ; i++) {
			for(int j = startC ; j < endC ; j++) {
				if(board[i][j] != tmp) {
					return -1;
				}
			}
		}
		
		return tmp;
	}
		
	static void solution(int startR, int startC, int endR, int endC) {
	
		int result = canPress(startR, startC, endR, endC);
		if(result != -1) {
			sb.append(result);
			return;
		}
		
		sb.append("(");
		int divR = (endR - startR) / 2;
		int divC = (endC - startC) / 2;
		
		solution(startR, startC, startR + divR, startC + divC);
		solution(startR, startC + divC, startR + divR, endC);
		solution(startR + divR, startC, endR, startC + divC);
		solution(startR + divR, startC + divC, endR, endC);		
		sb.append(")");
		
	}
}