165. 1992(쿼드트리) - 자바

import java.util.*;
import java.io.*;

class Main {
	static int[][] paper;
	static ArrayList<String> result;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		paper = new int[N][N];
		result = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			String[] tmp = br.readLine().split("");
			for (int j = 0; j < N; j++) {
				paper[i][j] = Integer.parseInt(tmp[j]);
			}
		}

		find(0, 0, N);
		System.out.println(String.join("", result));
	}

	private static void find(int x, int y, int N) {
		int color = paper[x][y];
		for (int i = x; i < x + N; i++) {
			for (int j = y; j < y + N; j++) {
				if (color != paper[i][j]) {
					result.add("(");
					find(x, y, N / 2);
					find(x, y + N / 2, N / 2);
					find(x + N / 2, y, N / 2);
					find(x + N / 2, y + N / 2, N / 2);
					result.add(")");
					return;
				}
			}
		}
		if (color == 0)
			result.add("0");
		else
			result.add("1");
	}
}

문제요약

각 4개의 각 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현하라.

설명

분할정복에 대해서는 아래를 참고하자.

https://smhope.tistory.com/432?category=1056187 

[알고리즘 | 자료구조] 분할정복

이 문제는 아래 문제와 크게 다르지 않다.

https://smhope.tistory.com/434

164. 2630 (색종이 만들기) - 파이썬

똑같이 4개의 영역을 나누고, N*N의 온전한 사각형이 만들어 지면 그 값을 하나의 온전한 사각형으로 생각한다.

					find(x, y, N / 2);
					find(x, y + N / 2, N / 2);
					find(x + N / 2, y, N / 2);
					find(x + N / 2, y + N / 2, N / 2);

각 1사분면,2사분면,3사분면,4사분면으로 하여 처리할 것이다.

처리가 시작하면 괄호를 열어야 한다. 때문에 아래 코드를 추가해줄것이다.

					result.add("(");

또한 처리가 끝나면 괄호를 닫아주어야 하므로 다음코드도 추가된다.

					result.add(")");

이를 합치면 다음과 같아진다.

					result.add("(");
					find(x, y, N / 2);
					find(x, y + N / 2, N / 2);
					find(x + N / 2, y, N / 2);
					find(x + N / 2, y + N / 2, N / 2);
					result.add(")");