[BAEKJOON 백준] 1992 쿼드트리

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

1992번: 쿼드트리

쿼드트리는 배열을 압축하는 문제입니다.

 

크기를 점점 반으로 나눠가면서 해당구역이 모두 같은 숫자가 될때까지 쪼개는 작업을 하게 됩니다.

 

그렇게 쪼개진 구역이 모든 같은 숫자가 나오면 그 숫자를 출력하게 됩니다.

 

import java.util.Scanner;

public class Main {

	static int N, M;
	static int arr[][];

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		arr = new int[N][N];

		for (int i = 0; i < N; i++) {
			String temp = sc.next();

			for (int j = 0; j < N; j++) {
				arr[i][j] = temp.charAt(j) - '0'; // 입력을 받아서 '0'을 빼 숫자로 바꿔준다.
			}
		}

		find(0, 0, N);

	}

	private static void find(int x, int y, int size) { // 크기를 반으로 계속 줄여가면서 압축하기
		// TODO Auto-generated method stub
		if (check(x, y, size)) { // check를 통해 한구역에 다 같은 숫자인지 확인
			System.out.print(M);
			return;
		} else {
			System.out.print("(");
			int newsize = size / 2;
			for (int i = 0; i < 2; i++) { // 크기를 반으로 나누고 재귀를 통해 결과값 찾기
				for (int j = 0; j < 2; j++) {

					find(x + newsize * i, y + newsize * j, newsize);
				}
			}
			System.out.print(")");
		}

	}

	private static boolean check(int x, int y, int size) {
		// TODO Auto-generated method stub
		int temp = arr[x][y];
		for (int i = x; i < x + size; i++) {
			for (int j = y; j < y + size; j++) {
				if (arr[i][j] != temp)
					return false;
			}
		}
		M = temp;
		return true;
	}

}