[Baekjoon 1992번/JAVA] 쿼드 트리

Question

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

1992번: 쿼드트리

 

---

💡 Solution

주어진 영상이 모두 0이거나 모두 1이어야 영상을 압축할 수 있으며, 0과 1이 섞여있다면 영상을 4개로 나누어 다시 각각의 영상이 모두 0 혹은 1로만 이루어져 있는지 확인하고 압축하는 방식을 거칩니다. 즉 아래와 같은 과정을 반복합니다.

 

1. 영상이 모두 0이거나 1로만 이루어져 있는지 확인한다.

2. 모두 0이거나 1이라면, 영상을 압축한다. 

3. 0과 1이 섞여있다면 영상을 4개로 나누고, 나누어진 각각의 영상마다 다시 1단계를 수행한다.

 

사실, 백준의 "색종이 만들기" 문제를 풀어봤다면 문제 이해는 금방 되지만 결과를 어떻게 도출한 건지 이해가 바로 되지 않았습니다. 하지만 그림으로 그려보니 금방 이해가 가더라구요 ..😂 

 

그리고 영상을 4개로 분할할 때 분할 순서(왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래)에 유의하셔야 됩니다! 순서에 따라 정답도 달라지기 때문입니당.

 

💻 Code

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

public class BJ1992 {
	static int N;
	static int[][] arr;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		arr = new int[N][N];
		for(int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < N; j++) {
				arr[i][j] = str.charAt(j) - '0';
			}
		}
		partition(0, 0, N);
		System.out.println(sb);
	}
	
	public static void partition(int row, int col, int size) {
		if (isSameColor(row, col, size)) {
			sb.append(arr[row][col]);
			return;
		}
		
		// 새로 분할할 때마다 ()를 추가해야한다.
		sb.append('(');
		
		int partitionSize = size / 2;
		partition(row, col, partitionSize);
		partition(row, col + partitionSize, partitionSize);
		partition(row + partitionSize, col, partitionSize);
		partition(row + partitionSize, col + partitionSize, partitionSize);
		
		sb.append(')');
	}
	
	public static boolean isSameColor(int row, int col, int size) {
		int color = arr[row][col];
		
		for (int i = row; i < row + size; i++) {
			for (int j = col; j < col + size; j++) {
				if (arr[i][j] != color) {
					return false;
				}
			}
		}
		
		return true;
	}

}