[백준 1992] 쿼드트리 (JAVA)

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

1992번: 쿼드트리

 

이번 포스팅에서는 분할정복을 사용하는 문제를 다뤄보도록 하겠다.

 

먼저 분할정복 알고리즘이란,

 

https://ko.wikipedia.org/wiki/%EB%B6%84%ED%95%A0_%EC%A0%95%EB%B3%B5_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

분할 정복 알고리즘 - 위키백과, 우리 모두의 백과사전

 

그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법

 

 

다음과 같이 정의 되어있다.

 

현재 문제를 예를 들어 보자면 N*N 크기의 정사각형을 탐색해

뭉쳐져 있는 구간별로 압축해 문자열로 바꾸어 출력하는 것인데

 

문제에서 주어진 뭉쳐진 구간의 기준이 왼쪽상단, 오른쪽 상단, 왼쪽하단, 오른쪽 하단으로 나누어 보면되는 것으로

이런 경우 분할정복 알고리즘을 사용하기 좋은 예인 것이다.

 

조금 간단한 예시를 들어 설명하자면,

 

 

위 그림과 같은 4*4 크기의 정사각형이 주어지고

이를 문제에서 주어진 기준에 따라 압축해 문자열로 변환하는 과정을 생각해보겠다.

 

먼저 모든 숫자가 동일하다면 단순히 1 또는 0으로 압축되고 끝날것이므로

좌측 상단부터 모두 동일한 숫자인지 확인하는 작업이 필요할것이다.

 

이때의 동일한 숫자인지 비교할 기준은

항상 좌측 상단부터 탐색을 진행하므로 좌측 최상단의 해당하는 부분을 기준으로 삼는다.

 

즉 현재 그림에서는 0이 될것이다.

 

그렇게 비교하던중 1번째 행 4번째 열에서 다른 숫자인 1을 찾게 된다면

현재 탐색을 진행하는 사각형은 모두 동일한 숫자가 아님을 확인하게 되고,

이 경우 분할하여 탐색을 진행하게 된다.

 

분할의 기준은 문제에서 주어진 기준인 왼쪽상단, 오른쪽 상단, 왼쪽하단, 오른쪽 하단

이렇게 4분할 하는데 그림으로 나타내면 다음과 같다.

 

 

 

이렇게 분할된 각 사각형을 이제 다시 탐색하게 되는데 이때 각 사각형의 크기는 2*2의 크기를 갖게 된다.

 

왼쪽 상단의 사각형은 탐색 진행시 모두 동일한 숫자를 갖는 것을 확인할수 있고 이는 0으로 압축된다.

 

이후 오른쪽 상단의 사각형은 탐색 진행시 다른 숫자를 갖는 것을 확인 후 다시 분할 하게 된다.

 

이를 그림으로 표현하면 다음과 같이 표현할 수 있다.

 

 

이렇게 2*2로 나뉜 사각형중 오른쪽 상단의 사각형을 분할하면 이제 사각형의 최소단위인 1*1 크기의 사각형으로

분할되는것을 확인 할수 있으며,

 

이때는 압축이 불가능하므로 순서대로 각 숫자를 가져오게 된다. >> 0 1 1 1

 

그리고 이전의 2*2의 크기로 나뉜 사각형중 왼쪽 하단의 사각형을 탐색한다.

 

같은 과정으로 왼쪽 하단, 오른쪽 하단의 사각형을 탐색하여 

 

각각 1 , 0 0 1 1 이란 결과를 얻어 낼수 있으며

 

모든 분할과 탐색이 끝난 사각형을 그림으로 표현하면 다음과 같다.

 

 

이는 문자열로 표현하면 (0 (0111) 1 (0011)) 로 표현된다.

 

 

그럼 이제 이를 코드로 구현 해보도록 하겠다.

 

먼저 각 좌표로서 사각형을 표현할 2차원 배열, 그리고 문자열에 대해 순차적으로 저장하기 위한

StringBuilder 객체를 선언해주도록 하겠다.

 

	static char[][] metrix;
	static StringBuilder sb = new StringBuilder();

 

 

이제 분할 정복 메소드를 작성해보겠다.

 

먼저 이 메소드는 재귀로 구현할 것이므로 재귀 호출시 탐색을 시작할 왼쪽최상단에 해당하는 좌표,

그리고 탐색할 현재 사각형의 크기를 인자값으로 받아야 한다.

 

	static void quadTree(int n, int x, int y) {

	}

 

그리고 더 이상 분할할수 없는 최소 단위인 1*1 크기의 사각형인 경우 리턴해줄수 있도록 해야한다.

이때 현재 사각형의 숫자를 StringBuider 객체에 저장한다.

 

	static void quadTree(int n, int x, int y) {
		char flag = metrix[x][y];
		if(n == 1) {
			sb.append(flag);
			return;
		}
	}

 

 

다음으론 분할이 가능한 사각형인 경우이다.

탐색을 진행하며 기준인 현재 사각형의 왼쪽 최상단 좌표에 해당하는

숫자와 다른 경우 메소드를 재귀호출해 사각형을 분할하도록 한다.

 

이때 재귀 호출 전후로 괄호를 StringBuider 객체에 저장해 사각형의 분할 시작과 끝을 구분해준다.

 

그리고 탐색이 모두 끝날때 까지 기준과 다른 사각형이 없는 경우엔 모두 동일한 숫자를 갖고 있단 것이므로

기준을 StringBuider 객체에 저장한다.

 

	static void quadTree(int n, int x, int y) {
		char flag = metrix[x][y];
		if(n == 1) {
			sb.append(flag);
			return;
		}
		int half = n >> 1;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(metrix[x + i][y + j] != flag) {
					sb.append('(');
					quadTree(half,x,y);
					quadTree(half,x ,y + half);
					quadTree(half,x + half,y);
					quadTree(half,x + half,y + half);
					sb.append(')');
					return;
				}
			}
		}
		sb.append(flag);
	}

 

그럼 위의 예시로 든 그림이 예상한 문자열로 압축되는지 확인 해보면,

 

 

정확한 결과를 내는 것을 확인 할 수 있다.

 

아래는 코드의 전문이다.

 

package boj4;

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

public class Boj1992 {
	
	/*
	 * 제출 完
	 */
	
	static char[][] metrix;
	static StringBuilder sb = new StringBuilder();
	
	static void quadTree(int n, int x, int y) {
		char flag = metrix[x][y];
		if(n == 1) {
			sb.append(flag);
			return;
		}
		int half = n >> 1;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(metrix[x + i][y + j] != flag) {
					sb.append('(');
					quadTree(half,x,y);
					quadTree(half,x ,y + half);
					quadTree(half,x + half,y);
					quadTree(half,x + half,y + half);
					sb.append(')');
					return;
				}
			}
		}
		sb.append(flag);
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(in.readLine());
		
		metrix = new char[n][n];
		
		for(int i = 0; i < n; i++) {
			String input = in.readLine();
			for(int j = 0; j < n; j++) {
				metrix[i][j] = input.charAt(j);
			}
		}
		
		in.close();
		
		quadTree(n,0,0);
		
		System.out.print(sb);
	}
	

}