[BOJ] 1992 쿼드트리 - Java

문제

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

1992번: 쿼드트리

 

---

풀이

• 영상의 크기를 나타내는 N의 크기만큼 검사하여 특정 구역의 모든 숫자가 같다면 그대로 압축
• 숫자가 같지 않다면 구역을 4등분하여 다시 검사 후 압축 진행
• 새로운 구역을 나눠서 검사할 때 ( 괄호 넣어주고, 검사 후 ) 괄호 넣어주기

코드

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

public class Main {
    static int[][] map;
    static StringBuilder sb;
    public static void zone(int r, int c, int div){
        if(check(r,c,div)){
            if(map[r][c] == 1) sb.append(1);
            else sb.append(0);
            return;
        }

        int n_div = div/2;
        sb.append("(");
        
        zone(r,c,n_div);
        zone(r,c+n_div, n_div);
        zone(r+n_div, c, n_div);
        zone(r+n_div, c+n_div, n_div);
        sb.append(")");
    }

    public static boolean check(int r, int c, int div){
        int first = map[r][c];

        for(int i=r; i<r+div; i++){
            for(int j=c; j<c+div; j++){
                if(map[i][j] != first) return false;
            }
        }

        return true;
    }

    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());

        map = new int[n][n];

        for(int i=0; i<n; i++){
            String s = br.readLine();
            for(int j=0; j<n; j++){
                map[i][j] = s.charAt(j)-'0';
            }
        }
        
        zone(0,0,n);

        System.out.println(sb);
    }
}

• 특정 구역의 행과 열 좌표를 주고, 구역의 모든 숫자가 같은지 검사
• 같다면 그대로 압축, 같지 않다면 구역 나누기
• 검사 순서는 2,1,3,4사분면 순서로 진행하기