[BOJ] 1992 쿼드 트리

쿼드트리

풀이

• 주어진 영상이 모두 0이 되거나 1로 되어 있으면 "0", "1"로 압축할 수 있고, 그게 아니라면 4등분하여 압축을 반복한다.

• 1708 종이의 개수랑 거의 똑같은 문제인데, 4등분 시도 하기 전에 "("를 넣어주고, 끝날 때 ")"를 넣어줘야 한다는 부분이 다름.

  정답 풀이

  import java.util.*;
  import java.io.*;
  public class Main {
      static int[][] map;
      static StringBuilder sb;
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          int N =  Integer.parseInt(br.readLine());
          map = new int[N][N];
          for(int i=0;i<N;i++){
              String str = br.readLine();
              String[] arr = str.split("");
              for(int j=0;j<N;j++){
                  map[i][j] = Integer.parseInt(arr[j]);
              }
          }
          sb = new StringBuilder();
          cur(N,0,0);
          System.out.println(sb);
      }
      private static void cur(int n,int i, int j){
          //같은수로만 이루어졌는지 확인
          boolean isFind = true;
          int start = map[i][j];
          L:for(int l=i;l<i+n;l++){
              for(int m=j;m<j+n;m++){
                  if(start!=map[l][m]){
                      isFind = false;
                      break L;
                  }
              }
          }
          if(!isFind){
              //왼위,오위,왼아,오아
              int newSize = n/2;
              sb.append("(");
              cur(newSize,i,j);
              cur(newSize,i,j+newSize);
              cur(newSize,i+newSize,j);
              cur(newSize,i+newSize,j+newSize);
              sb.append(")");
          }
          else{
              //같은거로만 이루어짐
              sb.append(start);
          }
      }
  }

• 종이의 개수 문제와 로직이 똑같다.