[백준(Baekjoon)][자바(java)] 1992 : 쿼드트리 / 분할 정복

 

www.acmicpc.net/problem/1992

1992번: 쿼드트리

 

( 이전 문제(색종이)랑 비슷한듯 )

 

 

< 문제의 포인트 >

 

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

 

 

< 문제 풀이 >

 

* 배열 입력받을 때 값 사이의 공백이 없으므로 주의

* 문자를 그때 그때 추가하여 문자열을 한꺼번에 출력할 수 있도록 StringBuilder 사용

 ( 바로 출력해도 되는데 속도가 더 느려질 수 있음 )

 

시작점 : x = 0, y = 0

길이 : len = n

 

n*n의 배열을 (x, y)부터 len*len 만큼 이중루프를 돌아 탐색하며 시작점이 나머지 다른 점들과 색이 같은지 판별 ( 0 - 흰, 1 - 검 )

다르면? 루프에서 빠져나와 앞 뒤 괄호 문자 StringBuilder에 추가( or 바로 출력 ),

그 사이에 (len/2)*(len/2) 크기 네 개로 나누어 recursion  ( len이 0이면 recursion 종료 -- base case )

같으면? 0일 경우 '0', 1일 경우 '0' StringBuilder에 추가

 

 

import java.util.Scanner;

public class Main {
	
	static int arr[][];
	static StringBuilder sb = new StringBuilder();
	
	public static void compression( int x, int y, int len ) {
		if( len == 0 ) 
			return;
		boolean isDiff = false;
		loop:
		for( int i = x; i < x+len; i++ ) {
			for( int j = y; j < y+len; j++ ) {
				if( arr[x][y] != arr[i][j] ) {
					isDiff = true;
					break loop;
				}
			}
		}
		if( isDiff ) {
			sb.append('(');
			compression( x, y, len/2 );
			compression( x, y+len/2, len/2 );
			compression( x+len/2, y, len/2 );
			compression( x+len/2, y+len/2, len/2 );
			sb.append(')');
		}
		else {
			if( arr[x][y] == 0 )	sb.append(0);
			else					sb.append(1);
		}
	}

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); sc.nextLine();
		arr = new int[n][n];
		for( int i = 0; i < n; i++ ) {
			String s = sc.nextLine();
			for( int j = 0; j < n; j++ )
				arr[i][j] = s.charAt(j)-'0';
		}
        
		compression( 0, 0, n );
        
		System.out.println( sb );
		sc.close();
	}
}