백준 1992 쿼드 트리 (Java)

1. 문제 링크

1992번: 쿼드트리

 

2. 문제 및 입출력예제

 

3. 문제 풀이

N이 언제나 2의 제곱수라는 것에서 분할 정복을 해야한다고 생각했다.

 

왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서로 압축이 된다고 하니 4분면으로 나누고 재귀를 했다.

=> round 메서드 (시작 x 좌표, 시작 y 좌표, 탐색할 길이)

 

만약 4분면이 모두 동일한 값이라면 재귀를 하지 않고 값을 내보낸다.

=> same 메서드 (시작 x 좌표, 시작 y 좌표, 검사할 길이)

 

 

4. 코드

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

public class Main {
	static int N;
	static String[][] tf;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		tf = new String[N][N];
		
		for(int i=0;i<N;i++) {
			String[] temp = br.readLine().split("");
			for(int j=0;j<N;j++) {
				tf[i][j] = temp[j];
				
			}
		}
		
		round(0, 0, N);
		System.out.println(sb);
		
	}

	private static void round(int x, int y, int n) {
		if(same(x, y, n)) {
			sb.append(tf[x][y]);
		}
		else {
			int half = n/2;
			sb.append("(");
			round(x, y, half);
			round(x, y+half, half);
			round(x+half, y, half);
			round(x+half, y+half, half);
			sb.append(")");
		}
	}

	private static boolean same(int x, int y, int n) {
		if(n == 1) { //1개짜리
			return true;
		}
		else {
			String first = tf[x][y];
			for(int i=x;i<x+n;i++) {
				for(int j=y;j<y+n;j++) {
					if(!tf[i][j].equals(first)) {
						return false;
					}
				}
			}
		}
		return true;
	}
}