백준 1992 쿼드트리 [JAVA]

문제 해석

• 해당 문제는 전 POST였던 2630-색종이만들기(JAVA)와 풀이방식이 매우 유사한 문제였다.
• 색종이를 쪼갰을 때 1~4사분면으로 쪼갠 것과 같은 방식으로 분할하고, 압축할 때도 색종이의 내부 요소가 같은 글자인지 판단하는 로직을 그대로 쓰면 되는 것이기 때문에 크게 어려움없이 풀 수 있는 문제이다.
• 문제 풀이에 앞서 쿼드트리가 무엇인지 알아야하는데 간단히 요약하자면 자식노드를 4(Quad:쿼드)개로 가지는 트리를 의미한다.
• 그림으로 설명하면 아래와 같다.
  
• 즉 식으로 표현하면 아래와 같이 표현할 수 있다.

(0(0011)(0(0111)01)1)

• 여기서 중요한 점은 분할을 할때마다 자식노드를 4개식 만들게 되고 노드 깊이가 더 깊어진다.
• 즉, 노드의 깊이가 깊어질 때 '( )' 괄호로 감싼다는 것을 알 수 있다.

//분할할때마다의 깊이 시작 부분에 괄호 끝부분에 괄호해서 묶어줌
sb.append('(');
cutVideo(row, col, mSize);                    
cutVideo(row, col+mSize, mSize);           
cutVideo(row+mSize, col, mSize);          
cutVideo(row+mSize, col+mSize, mSize); 
sb.append(')');

• 분할 앞뒤로 괄호를 넣어주었다!

코드

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

public class Main {
    static int[][] video; //정사각형 색종이 색 구별(1과 0으로)
    static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine()); //영상의 크기

        video = new int[N][N]; //영상 데이터 구성

        for(int i = 0; i < N; i++){ //영상 구성 데이터 입력받기
            String str = br.readLine(); //한줄이 숫자 하나로 받기 때문에 (띄어쓰기가 없음)

            for(int j = 0; j < N; j++){
                // char :  단 한 글자만 저장할 수 있는 변수 한글자만을 빼야하기 때문
                // '0'의 아스키코드값은 48로 0이 나오면 48 -48 = 0 이 저장
                // '1'의 아스키코드값은 49로 1이 나오면 49 - 48 = 1이 저장
                video[i][j] = str.charAt(j) - '0'; //문자를 '0'으로 빼서 0 혹은 1만 나오게 함
            }
        }

        br.close();

        cutVideo(0, 0, N);

        System.out.println(sb);
    }

    static void cutVideo(int row, int col, int size){//영상 분할(0으로만, 1로만 이루어지도록)

        if(chkVideo(row, col, size)){  //만약
           sb.append(video[row][col]);
           return;
        }

        //4개로 줄이기 위해
        int mSize = size/2; //절반 사이즈 (left+right)/2와 같은 역할을 함 (압축이 불가능 하므로)

        //분할할때마다의 깊이 시작 부분에 괄호 끝부분에 괄호해서 묶어줌
        sb.append('(');
        cutVideo(row, col, mSize);                      // 출력 순서 1
        cutVideo(row, col+mSize, mSize);            // 출력 순서 2
        cutVideo(row+mSize, col, mSize);           //  출력 순서 3
        cutVideo(row+mSize, col+mSize, mSize); // 출력 순서 4
        sb.append(')');
    }

    static boolean chkVideo(int row, int col, int size){ //영상 데이터 확인
        int data = video[row][col]; // (row, col)을 기준으로 data 확인

        for(int i = row; i < row+size; i++){
            for(int j = col; j < col+size; j++){
                if(video[i][j] != data){ //처음 기준 data와 다르면
                    return false;
                }
            }
        }
        
        return true; //모두 같은 data이면
    }
}

결과

느낀 점

문제는 크게 어렵지 않았다. 확실히 색종이 만들기 문제와 너무 유사해서 살짝만 코드를 바꿔주면 크게 어려움이 없는 문제였다. 여기선 1~4사분면 개념이 아녀서 그거 순서바꾸는 거랑 괄호 앞뒤로 추가하는 정도? 그 정도만 고치면 문제없이 풀리는 문제였던 것 같다. (데이터 입력 받는 건 기본이니까,,,)