[백준] 1992 - 쿼드 트리 JAVA

Solved.ac Class 완전정복 프로젝트

Class : 3 ~ 2 ++

 

---

링크

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

문제

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(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분할 하여, 다시 압축을 시도하여, 그 결과를 출력하는 문제이다. 동일한 처리를 크기만 쪼개어 반복하므로, 재귀적 처리를 생각해야한다. 이 점을 인지하고 풀이로 들어가자.

 

 

 

c.f)해당 문제의 접근은 1780번 문제와 동일한 재귀의 문제이다. 이문제가 어렵다면, 저 문제를 풀어보는 것도 나쁘지 않다.

https://j-sik.tistory.com/65

[백준] 1780 - 종이의 개수 JAVA

풀이

 문제가 이해가 안된다면 그려보는것도 좋다. 나는 다음과 같이 간단하게 그렸다. 

 

먼저 전체를 검색한 뒤, 압축을 할 수 없으므로 쪼갠다. 4개로 쪼개진 영상을 각각 압축을 할 수 있는지 없는지 판단한다.

이런식의 반복을 통해 값을 구하는 것은 어렵지 않다. 본인의 경우, 괄호 삽입 때문에 시간을 오래 썼다. 문제에서 괄호는 언제 쓰느냐 타이밍을 잡는 것이 중요하다. 문제에서 괄호는 쪼개지면, 괄호를 연다. 열고 4분할된 영역의 압축이 모두 끝나면, 닫는다. 이 타이밍을 정확히 알아야 단시간에 빠르게 문제 해결을 할 수 있다.

 

 해당 결과는 Stringbuilder를 이용하여, 데이터를 누적하고 출력하였다.

 

 

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        Main test = new Main();
    }

    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer stk;
        int len = Integer.parseInt(br.readLine());
        int[][] data = new int[len][len];

        for (int i = 0; i < len; i++) {
            String rows = br.readLine();
            int j = 0;
            for (char row : rows.toCharArray()) {
                data[i][j] = row-48;
                j++;
            }
        }

        solution(data, sb,len,0,0);

        System.out.println(sb);
    }

    private void solution(int[][] data, StringBuilder sb,int len,int start_x,int start_y) {


        //전체 검색
        if (isSame(data,len,start_x,start_y)){

            sb.append( data[start_x][start_y] );
        }else{
            //만약 일치하지 않는다면 4개로 쪼개서 재귀

                sb.append("(");

                solution(data,sb,len/2,start_x,start_y);
                solution(data,sb,len/2,start_x,start_y+len/2);
                solution(data,sb,len/2,start_x+len/2,start_y);
                solution(data,sb,len/2,start_x+len/2,start_y+len/2);


                sb.append(")");
            

        }





    }

    private boolean isSame(int[][] data,int len ,int start_x,int start_y){
        int toggle =0;
        for (int i = start_x ; i < start_x+len ; i++){
            for (int j = start_y ; j < start_y+len ; j++){
                //첫값과 다른게 있으면 모두 false
                if((i == start_x)&& (j == start_y)){
                    toggle = data[i][j];
                }else{
                    if( data[i][j] !=toggle){
                        return  false;
                    }
                }
            }
        }
        return true;
    }

}

결과

 

 

 타이밍을 머릿속으로 그려봐야한다. 본인의 경우 원하는 대로 괄호가 안나온 것을 확인한 뒤, 자꾸 디버깅으로 찾으려는 아주 못된 습관이 있는데 이 때문에 처음 로직을 짤 때 보다 수정할 때 시간이 배로 걸렸다. 항상 논리를 세우고, 그것을 코딩하면서, 논리와 구현이 일치될 수 있는 훈련이 중요하고 느낀다. 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.