[백준] 1992번 : 쿼드트리

문제

 

위와 같은 0과 1로 이루어진 영상의 정보가 담긴 배열이 주어졌을 때

영상이 같은 색깔로만 이루어진 경우에는 압축이 가능하고

그렇지 않은 경우에는 영상을 4등분 하여 압축이 가능한지 계속해서 확인하여

영상을 압축한 결과를 출력하라

 

접근 방식

(0(0011)(0(0111)01)1)

 

문제의 예시 그림 같은 경우에는 위와 같은 형태로 압축이 가능한데

1780, 2630번 문제를 풀어봤다면 이번 문제 역시 쉽게 풀 수가 있다.

 

영상의 가로, 세로 길이는 항상 2의 k제곱 형태를 유지하기 때문에

영상을 4등분 하는 것은 이전 문제들을 풀던 것처럼 재귀를 돌 때마다

길이를 절반 나눠주면 된다.

 

 

위 이미지처럼 검은색 > 빨간색 > 파란색 순서로 재귀 호출을 하면서

현재 범위가 모두 같은 수로만 이루어져 있는지 확인해 주면 된다.

 

이전 문제들과 다른 점은 소괄호로 재귀의 깊이를 구분해주는 것인데

괄호가 어떤 상황에서 열리고 닫히는지만 생각해보면 어려울건 없다.

 

풀이

public class Main {

	private static int[][] arr;
	private static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		arr = new int[n][n];

		for (int i = 0; i < n; i++) {
			String[] videos = br.readLine().split("");
			for (int j = 0; j < n; j++) {
				arr[i][j] = Integer.parseInt(videos[j]);
			}
		}

		compression(0, 0, n);

		System.out.println(sb);
	}

	private static void compression(int start, int end, int size) {
		if (verification(start, end, size)) {
			if (arr[start][end] == 0) {
				sb.append("0");
			} else {
				sb.append("1");
			}

			return;
		}

		sb.append("(");

		int half = size / 2;

		for (int i = start; i < start + size; i += half) {
			for (int j = end; j < end + size; j += half) {
				compression(i, j, half);
			}
		}

		sb.append(")");
	}

	private static boolean verification(int start, int end, int size) {
		int now = arr[start][end];

		for (int i = start; i < start + size; i++) {
			for (int j = end; j < end + size; j++) {
				if (arr[i][j] != now) {
					return false;
				}
			}
		}

		return true;
	}
}