백준 1992번-쿼드트리(JAVA)

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

1992번: 쿼드트리

 

쿼드트리 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

128 MB

21244

12807

10022

59.815%

문제

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(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의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

출력

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

 

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

public class quadtree {
	static char[][] map;
	static String[] arr;
	static String[][] upper;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		map = new char[N][N];
		for (int i = 0; i < N; i++) {
			char[] line = br.readLine().toCharArray();
			for (int j = 0; j < N; j++) {
				map[i][j] = line[j];
			}
		}
        //N=1인 경우 예외 처리
		if(N == 1) {
			System.out.println(map[0][0]);
			return;
		}
		
        //N을 2의 지수로 변경
		int k = 0;
		while (N != 1) {
			N /= 2;
			k++;
		}
		N = k;

        //현재 string 배열
		arr =new String[4];
		//상위 string 배열
        upper =new String[N][4];
		visit(0, 0, N, 0);
		System.out.println(upper[N-1][0]);
	}

	static void visit(int row, int col, int cnt, int p) {
		if (cnt == 0) {
			arr[p] = Integer.toString(map[row][col]-48);
			return;
		}
		int t = (int) Math.pow(2, cnt - 1);

		//z모양 탐색
		visit(row, col, cnt - 1, 0);
		visit(row, col + t, cnt - 1, 1);
		visit(row + t, col, cnt - 1, 2);
		visit(row + t, col + t, cnt - 1, 3);
		
        //모두 같은지를 나타내는 flag(0: 모두 같음, 1: x)
		int flag = 0;
		for (int i = 0; i < 3; i++) {
        	//괄호를 포함하는 경우는 다르다고 간주하여 flag=1, break;
			if(arr[i].contains("(") || arr[i+1].contains("(")) {
				flag =1;
				break;
			}
            //arr의 원소가 하나라도 다르면 flag =1, break;
			if (arr[i].compareTo(arr[i + 1]) != 0) {
				flag = 1;
				break;
			}
		}
        
		String str = new String();
		//모두 같지 않은 경우
        if (flag != 0) {
        //괄호와 함께 현재 배열에 있는 원소들을 더해 str을 만들어 준다.
			str+="(";
			for (String s : arr) {
				str += s;
			}
			str+=")";
		}
        //모두 같은 경우
        else {
        //모두 같으므로 현재 배열의 0번으로 str을 만들어준다.
			str = new String(arr[0]);
		}
        //만들어진 str을 상위 스트링 배열의 [cnt-1][p] 인덱스에 저장해준다.
        //cnt-1= 배열의 층
        //p=사분면의 z순서 index
		upper[cnt-1][p] = new String(str);
        //사분면을 모두 탐색한 경우(p=3), 현재 배열에 현재배열을 압축한 값 저장
        //현재배열이 upper로 변경되어 1층 상위로 올라가게 된다.(더 상위 배열 탐색 가능)
		if(p ==3) {
			for(int i = 0; i < 4; i++) {
				arr[i] = new String(upper[cnt-1][i]);
			}
		}
        //가장 높은층까지 탐색을 마친경우, 결과 문자열이 upper[N-1][0]에 들어가게 된다.
        //따라서 line 38.처럼 출력
	}
}