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

문제

1992번: 쿼드트리

 

접근방식

현재의 시작점 x,y에서 size만큼 탐색하면서 중간에 다른 값이 없는 경우 flag를 true로 가지고 board의 값을 뽑아줌. 중간에 다른 값이 있는 경우 4분할하여 재귀를 돌면서 탐색함. 

풀이

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

public class Main {
	static int N,board[][];
	static StringBuilder answer = new StringBuilder();

	public static void DFS(int x,int y, int size) {
		if(size == 1) {
			answer.append(board[x][y]);
			return;
		}
		int start = board[x][y];
		boolean flag = true;
		
		for (int i = x; i < x+size; i++) {
			for (int j = y; j < y+size; j++) {
				if(board[i][j]!=start) {
					flag = false;
					break;
				}
			}
		}
		if(flag) {
			answer.append(start);
			return;
		}else {
			answer.append("(");
			for (int i = x; i <= x+size/2; i+=size/2) {
				for (int j = y; j <= y+size/2; j+=size/2) {
					DFS(i,j,size/2);
				}
			}
			answer.append(")");
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		board = new int[N][N];
		
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < N; j++) {
				board[i][j] = str.charAt(j)-'0';
			}
		}
		DFS(0,0,N);
		System.out.println(answer);
	}
}