백준 1992번 쿼드트리(java)

[Silver I] 쿼드트리 - 1992

문제 링크

성능 요약

메모리: 14708 KB, 시간: 144 ms

분류

분할 정복, 재귀

제출 일자

2024년 7월 28일 20:50:17

문제 설명

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다. N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

출력

영상을 압축한 결과를 출력한다.

 

풀이

분할 정복의 문제로 재귀함수를 무려 4개를 만들어야 한다.

 

필자는 다음과 같은 방식으로 해결했다.

1. 전체 배열에 들어있는 숫자들의 합을 구한다.
   1. 만약 합이 0이라면 바로 0을 출력하고 return 시킨다
   2. 만약 합이 n*n(모든 칸에 1이 들어있는 경우) 바로 1을 출력하고 return 시킨다
2. 현재 재귀 함수에 들어온 배열의 크기가 2*2라면 모두 출력하고 return 시킨다
3. 위의 모든 경우에 해당하지 않는다면, 배열을 1사분면, 2사분면, 3사분면,4사분면으로 나눠서 재귀호출 해야한다.

위와 같은 방식으로 배열을 4개로 쪼개가면서 전부 1이거나 0일 경우 바로바로 출력해주면 문제를 해결할 수 있다.

 

가장 많이 고민했던 건 괄호를 어느 타이밍에 출력해야 할까 였다.

 

필자는 배열을 4개의 사분면으로 쪼갤 때 "(" 를 한 번 출력해 주었고

 

쪼개서 들어갔을 때 배열의 총 크기가 4인 경우 "(" 를 출력하고 4개 원소를 전부 출력 이후 ")" 출력

 

4개의 사분면에서 모두 return 됐을 경우 ")" 출력 방식으로 해결했다.

 

간단히 생각해보면 사분면으로 쪼갤 때 "("와 ")"가 한 번씩 출력되면 되므로 위와 같이 출력해 주었다.

 

전체 코드

public class Main{
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N,cnt=0, x[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        x = new int[N][N];

        for(int  i=0 ;i<N;i++){
            char[] a = br.readLine().toCharArray();
            for(int  j = 0 ;j<N;j++){
                x[i][j] = Integer.parseInt(String.valueOf(a[j]));
            }
        }

        devide(0,N,0,N,N);

        bw.flush();

    }

    public static void devide(int left, int right, int up, int down, int n) throws IOException {
        int s = sum(left, right, up, down);
        if(s == 0){
            bw.write("0");
            return;
        }
        if(s == n*n){
            bw.write("1");
            return;
        }
        if(n == 2){
            bw.write("(");
            for(int  i = up;i<down;i++){
                for(int j=left;j<right;j++){
                    bw.write(String.valueOf(x[i][j]));
                }
            }
            bw.write(")");
            return;
        }
        bw.write("(");
        devide(left,(right+left)/2,up,(down+up)/2,n/2);
        devide((left+right)/2,right,up,(down+up)/2,n/2);
        devide(left,(right+left)/2,(down+up)/2,down,n/2);
        devide((left+right)/2,right,(down+up)/2,down,n/2);
        bw.write(")");


    }

    public static int sum(int left, int right, int up, int down){
        int s = 0;
        for(int i = up; i<down;i++){
            for(int j = left;j<right;j++){
                s += x[i][j];
            }
        }

        return s;
    }

}