[Java] 백준 1992번 쿼드트리

분할 정복 문제입니다.

사각형을 4개로 나누어서 조건에 부합하는지 확인합니다.
부합하지 않으면 부합할 때까지 나누어줍니다.

나누어진곳이 0으로 이루어졌다면 0을 출력하고 1로 이루어졌다면 1을 출력합니다.
나누어 질 때 ( )로 덮어 줍니다.

public static void Func(int y, int x, int size) {
    int num = map[y][x]; 
    for(int i=0; i<size; ++i) {
        for(int j=0; j<size; ++j) {
            if(map[y+i][x+j] != num) {
                ans += "(";
                Func(y, x, size/2);
                Func(y, x+size/2, size/2);
                Func(y+size/2, x, size/2);
                Func(y+size/2, x+size/2, size/2);
                ans += ")";
                return;
            } 
        }
    }
    ans += num == 0 ? "0" : "1";
}

 

전체 코드

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

public class Main {
	static int n;
	static String ans = "";
	static int[][] map;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		for(int i=0; i<n; ++i) {
			String s = br.readLine(); 
			for(int j=0; j<n; ++j) {
				map[i][j] = s.charAt(j) == '0' ? 0 : 1;
			}
		}
		Func(0, 0, n);
		bw.write(ans);
		bw.close();
	}
	public static void Func(int y, int x, int size) {
		int num = map[y][x]; 
		for(int i=0; i<size; ++i) {
			for(int j=0; j<size; ++j) {
				if(map[y+i][x+j] != num) {
					ans += "(";
					Func(y, x, size/2);
					Func(y, x+size/2, size/2);
					Func(y+size/2, x, size/2);
					Func(y+size/2, x+size/2, size/2);
					ans += ")";
					return;
				} 
			}
		}
		ans += num == 0 ? "0" : "1";
	}
}