[백준, BOJ 1992] 쿼드트리 - 보스 제주뉴스

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

1992: 쿼드트리

첫 번째 줄에는 이미지의 크기를 나타내는 숫자 N이 있습니다.

N은 항상 2의 거듭제곱으로 지정되며 값 범위는 1 ≤ N ≤ 64입니다.

길이가 N인 문자열 N개는 두 번째 줄부터 입력됩니다.

각 문자열은 0 또는

'추천 관련글,

www.acmicpc.net

쉬운 목차

문제

흑백 이미지를 압축하여 표현하는 데이터 구조로 Quad Tree라는 방식이 있습니다.

하얀점 0, 검은점 1로만 구성된 영상(2D 배열)에 같은 번호의 많은 점이 한곳에 모여 있으면 압축이 가능하고 쉽게 쿼드 트리로 표현할 수 있다.

주어진 이미지가 모두 0으로 구성되어 있으면 압축 결과는 “0”이고 모두 존재하면 압축 결과는 “1”입니다.

0과 1이 섞이면 전체를 한 번에 표시할 수 없기 때문에 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래의 4개 프레임으로 나누어 압축하고 이 4개 영역을 압축한 결과가 순서가 된다.

괄호 안에 표시

위 그림에서 왼쪽 이미지는 오른쪽 배열처럼 숫자로 지정하고, 이 이미지를 쿼드트리 구조로 압축하면,(0(0011)(0(0111)01)1)“. N×N 크기의 이미지가 주어졌을 때 이 이미지를 압축한 결과를 출력하는 프로그램을 작성하세요.

기입

첫 번째 줄에는 이미지의 크기를 나타내는 숫자 N이 있습니다.

N은 항상 2의 거듭제곱으로 지정되며 값 범위는 1 ≤ N ≤ 64입니다.

길이가 N인 문자열 N개는 두 번째 줄부터 입력됩니다.

각 문자열은 0 또는 1의 숫자로 구성되며 이미지의 각 지점을 나타냅니다.

누르다

이미지 압축 결과를 반환합니다.

728×90

샘플 입력 1

예제 출력 1

((110(0101))(0010)1(0001))

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

public class Main {
	
	static char()() video; 
	
	private static String compress(int n, int x, int y) {
		if(n == 1) {
			return String.valueOf(video(x)(y));
		}
		
		String() v = new String(4);
		v(0) = compress(n / 2, x, y); // 왼쪽 위
		v(1) = compress(n / 2, x, y + n / 2); // 오른쪽 위
		v(2) = compress(n / 2, x + n / 2, y); // 왼쪽 아래
		v(3) = compress(n / 2, x + n / 2, y + n / 2); // 오른쪽 아래
		
		// 값의 길이가 1이고 모두 같으면
		if(v(0).length() == 1 && v(0).equals(v(1)) && v(1).equals(v(2)) && v(2).equals(v(3))) {
			return v(0); // 하나로 압축해서 리턴
		}
		else // 압축 불가능하면 괄호로 묶어서 리턴
			return "(" + v(0) + v(1) + v(2) + v(3) + ")";
	}

	public static void main(String() args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 영상 크기 입력
		int N = Integer.parseInt(br.readLine());
		// 영상 배열 입력
		video = new char(N)(N);
		for (int i = 0; i < N; i++) {
			video(i) = br.readLine().toCharArray();
		}
		
		String result = compress(N, 0, 0);
		
		// 출력
		System.out.println(result);
	}

}