[문제] 백준 1992번 쿼드트리

* 출처: www.acmicpc.net/problem/1992

1992번: 쿼드트리

내 생각

 

1. 첫번째 풀이

배열을 계속해서 4등분 쪼개나가면 되므로 재귀로 풀었다.

종료 조건은 해당 영역이 0또는 1로 가득 채워있으면 된다. 

그래서 종료 조건을 아래 3가지로 나눴다.

  1. 배열의 크기가 1일 때

  2. 1로 가득 찼을 때   

  3. 0으로 가득 찼을 때

 

가득 채운걸 확인하기 위해 메소드를 따로 만들었다.

시작하는 인덱스 위치와 배열의 크기를 인자로 받아 검사하도록 했다.

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N;
	static int[][] matrix;

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

		N = Integer.parseInt(in.readLine()); // matrix size
		matrix = new int[N][N];

		// init matrix
		for (int i = 0; i < N; i++) {
			String s = in.readLine();
			for (int j = 0; j < N; j++) {
				matrix[i][j] = s.charAt(j) - '0';
			}
		}
		quad(0, 0, N);
		// recursive function
		
		System.out.print(sb);
	}
//recursive func. size: 2의 제곱수
	static void quad(int x, int y, int size) {
		if (size == 1) {
			if (matrix[x][y] == 1)
				sb.append('1');
			else if (matrix[x][y] == 0)
				sb.append('0');
			return;
		}
		if (isFullZero(x, y, size)) {
			sb.append('0');
			return;
		}
		if (isFullOne(x, y, size)) {
			sb.append('1');
			return;
		}

		sb.append('(');
		int half = size/2;
		quad(x,y,half);
		quad(x, y+half,half);
		quad(x+half,y,half);
		quad(x+half,y+half, half);

		sb.append(')');
	}

	// 해당 영역이 0으로 가득차면 true
	static boolean isFullZero(int x, int y, int size) {
		for (int i = x; i < x + size; i++) {
			for (int j = y; j < y + size; j++) {
				if (matrix[i][j] != 0)
					return false;
			}
		}
		return true;
	}

	// 해당 영역이 1으로 가득차면 true
	static boolean isFullOne(int x, int y, int size) {
		for (int i = x; i < x + size; i++) {
			for (int j = y; j < y + size; j++) {
				if (matrix[i][j] != 1)
					return false;
			}
		}
		return true;
	}

}