[백준] 1992번 - 쿼드트리

 

분할정복(Divide & Conquer)기법을 사용한 문제이다.

https://ddamdoo.tistory.com/157

[백준] 2630번 - 색종이 만들기

 

위 링크의 문제와 비슷하게 풀이하면 된다. 배열에 입력된 값이 모두 통일된 값이 없으면 1/4단위로 쪼개어 모두 통일 된 값이 나오도록 하는 문제이다. 수식에서 쪼개는 함수를 실행하기 전에 결과를 출력할 문자열에 괄호를 열고, 함수를 모두 실행한 이후에 괄호를 닫는 것을 추가해주어 결과를 만들었다.

 

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

public class p1992 {
	public static int a;
	public static int[][] ary;
	public static String s = "";

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int a = Integer.parseInt(br.readLine());

		ary = new int[a][a];

		for (int i = 0; i < a; i++) {
			String[] s = br.readLine().split("");
			for (int j = 0; j < a; j++) {
				ary[i][j] = Integer.parseInt(s[j]);
			}
		}

		dq(ary, 0, 0, a);
		System.out.println(s);
	}

	public static void dq(int[][] n, int start, int end, int size) {
		int k = n[start][end];

		for (int i = start; i < start + size; i++) {
			for (int j = end; j < end + size; j++) {
				if (k != n[i][j]) {
					s += "(";

					dq(n, start, end, size / 2);
					dq(n, start, end + size / 2, size / 2);
					dq(n, start + size / 2, end, size / 2);
					dq(n, start + size / 2, end + size / 2, size / 2);

					s += ")";
					return;
				}
			}
		}
		if (k == 1) {
			s += "1";
		} else {
			s += "0";
		}
	}
}