[ Baekjoon ] 1992번 - 쿼드트리

1992번: 쿼드트리

 

풀이 방법

분할정복(Divide and Conquer)으로 푸는 문제이다. 해당 영역이 모두 0인지 혹은 모두 1인지 확인해 같으면 출력하고, 그렇지 않으면 상, 하, 좌, 우 4영역으로 나누어(divide) 정복(conquer)하는 STEP으로 이루어져있다.

 

구현 코드

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

public class Q_1992 {
	static int N;
	static int[][] array;
	static StringBuilder sb;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();
		
		N = Integer.parseInt(br.readLine());
		String s;
		
		array = new int[N][N];
		for (int i = 0; i < N; i++) {
			s = br.readLine();
			for (int j = 0; j < N; j++) {
				array[i][j] = Character.getNumericValue(s.charAt(j));
			}
		}
		
		divide(0, N-1, 0, N-1);
		
		System.out.print(sb);
	}
	
	public static void divide(int i_start, int i_end, int j_start, int j_end) {
		if (check(i_start, i_end, j_start, j_end)) { // 해당 영역의 숫자들이 모두 같으면
			sb.append(array[i_start][j_start]);
		} else {
			int i_mid = (i_start + i_end) / 2;
			int j_mid = (j_start + j_end) / 2;
			
			sb.append('(');
			divide(i_start, i_mid, j_start, j_mid); // 제 1사분면
			divide(i_start, i_mid, j_mid+1, j_end); // 제 2사분면
			divide(i_mid+1, i_end, j_mid+1, j_end); // 제 3사분면
			divide(i_mid+1, i_end, j_start, j_mid); // 제 4사분면
			sb.append(')');
		}
	}
	
	// 모두 0인지 혹은 모두 1인지 check
	public static boolean check(int i_start, int i_end, int j_start, int j_end) {
		int value = array[i_start][j_start]; // 영역의 시작점
		
		for (int i = i_start; i <= i_end; i++) {
			for (int j = j_start; j <= j_end; j++) {
				if (array[i][j] != value)
					return false;
			}
		}
		
		return true;
	}
}