[Java] 백준 1992. 쿼드트리

문제

1992번: 쿼드트리 (acmicpc.net)

1992번: 쿼드트리

풀이

풀이 알고리즘은 다음과 같다.

1. 주어진 크기 N에서 2중for 탐색으로 배열을 모두 1 인지 0 인지 검사를 한다.
2. 모두 1이거나 0 이면 1 또는 0 을 출력한다.
3. 그렇지 않으면, 재귀 탐색으로 subarray를 탐색을 구현한다.

 

 

코드

 

import java.io.*;
import java.util.*;

public class Main {
    int m[][];
    int ans;
    int theta;
    BufferedWriter bw;
    public static void main(String args[]) throws IOException {
        Main m = new Main();
        m.solution();
    }
    public void solution() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        String str;
        m = new int[N][N];
        for(int i = 0; i< N ;i++){
            str = br.readLine();
            for(int j = 0 ;j < N ;j ++){
                m[i][j] =str.charAt(j) -'0';
            }
        }
        recursiveF(N, 0, 0);
        bw.close();
    }
    public void recursiveF(int N , int x, int y)throws IOException{
        int n = check(x,y,N);
        if(n != -1 ){
            bw.write(Integer.toString(n));
        }else if( N/2 >0){
            bw.write("(");
            recursiveF(N/2, x, y);
            recursiveF(N/2, x, y + N/2);
            recursiveF(N/2, x + N/2, y);
            recursiveF(N/2, x+N/2, y+N/2);
            bw.write(")");
        }
    }
    public int check(int x, int y, int N){
        int z = 0;
        boolean f = false;
        for(int i = x; i< x + N ;i++){
            if(f)break;
            for (int j = y; j < y + N; j++) {
                if(f)break;
                if(m[i][j] != z){
                    f = true;
                }
            }
        }
        if(!f)return z;
        f = false;
        z = 1;
        for(int i = x; i< x + N ;i++){
            if(f)break;
            for (int j = y; j < y + N; j++) {
                if(f)break;
                if(m[i][j] != z){
                    f = true;
                }
            }
        }
        if(!f)return z;
        return -1;
    }

}