백준 1992 - 쿼드 트리(자바 - 분할정복)

이전 글에 이어서 또다시 분할 정복을 활용하는 쿼드 트리 문제이다.

사실 색종이 만들기 문제를 성공적으로 풀고 나서 너무 감격한 나머지, 이 쿼드 트리라는 개념을 완전히 내 것으로 만들기 위해 관련 문제를 더 풀어보았다.

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

1992번: 쿼드트리

 

색종이 만들기와 비슷하나 조금 다르다!

이 문제의 경우 기본적으로 분할 정복 알고리즘을 이용한 쿼드 트리 구현이라는 점에 있어서 색종이 만들기와 같으나 요구하는 답안이 달랐다.

 

이 문제는 다음과 같이 해결하였다.

- 현재 사분면의 모든 색깔이 일치하지 않는 경우 색종이 만들기 때와 같이 재귀 호출을 통해 4분할을 하는 과정을 수행해야 한다.

- 여기서 4분할을 할 때 결과값으로 되돌려줄 문자열에 "(" 를 추가해주어야 한다.

(문제를 봤을 때 4분할이 있을 때마다 괄호를 추가해줘야 하는 것으로 파악했다.)

- 4분할이 완료되면 ")" 를 결과값으로 되돌려줄 문자열에 추가해준다.

- 만약 각 재귀 함수 수행 결과 현재 사분면이 모두 하얀색으로 이루어져 있다면 문자열에 "0" 을 추가해준다.

- 마찬가지로 재귀 함수 수행 결과 현재 사분면이 모두 검은색으로 이루어져 있다면 문자열에 "1" 을 추가해준다.

 

코드는 다음과 같다.

- Main.java

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

public class Main {
	
	static char[][] quadTree = null;
	static String result = "";
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int count = Integer.parseInt(br.readLine());
		quadTree = new char[count][count];
		
		for(int i = 0; i < quadTree.length; i++) {
			String str = br.readLine();
			for(int j = 0; j < quadTree[i].length; j++) {
				quadTree[i][j] = str.charAt(j);
			}
		}
		
		divideAndconquer(0, count, 0, count);
		
		bw.write(result + "\n");
		bw.flush();
		bw.close();
	}

	private static void divideAndconquer(int x1, int x2, int y1, int y2) {
		
		char standard = quadTree[x1][y1];
		boolean colorCheck = true;
		
		for(int i = x1; i < x2; i++) {
			for(int j = y1; j < y2; j++) {
				if(standard != quadTree[i][j]) {
					colorCheck = false;
					break;
				}
			}
			
			if(!colorCheck)
				break;
		}
		
		if(colorCheck) {
			if(standard == '0')
				result += "0";
			else
				result += "1";
		}
		else {
			result += "(";
			divideAndconquer(x1, (x1+x2)/2, y1, (y1+y2)/2);
			divideAndconquer(x1, (x1+x2)/2, (y1+y2)/2, y2);
			divideAndconquer((x1+x2)/2, x2, y1, (y1+y2)/2);
			divideAndconquer((x1+x2)/2, x2, (y1+y2)/2, y2);
			result += ")";
		}
	}
}