백준 1992번 쿼드트리 분할정복 알고리즘 JAVA 자바

 

 

 

백준 1992번 쿼드트리 알고리즘은 분할정복 알고리즘 시리즈다. 전체의 문제를 작은 단위로 쪼개는 작업이 첫번째로 고려되어야 한다. 백준 1992번에서 제시된 쿼드트리는 압축 알고리즘으로 사용되는 방법 중 하나다. 동일한 점들이 모여있는 곳을 압축해서 간단하게 표현하는 방법이다. 쿼드 트리는 4개의 자식노드를 가진 트리구조다. 

 

주어진 문제에서 흑과 백으로 이루어진 N*N 정사각형이 있다고 하면, 동일한 값으로만 이뤄진 N*N 정사각형으로 분해를 하는 것이다. 만약 값이 다른 정사각형이 발견되면 4등분을 하게 되고 분할된 정사각형에서 동일한 작업을 이어가게 되는 것이다.

 

 

위에서 흑과 백이 동시에 존재하는 정사각형을 4등분하게 되면 왼쪽 위부터 1사분면, 오른쪽 위를 2사분면, 왼쪽 아래를 3사분면, 오른쪽 아래를 4사분면으로 지정하고, 순서대로 재귀 알고리즘이 작동된다.

4개의 구역을 재귀 메소드로 확인하는 작업을 거치면 0으로만 이뤄진 구역을 찾게 되고, 재귀 프로세스는 종료된다. 재귀 깊이가 한번 깊어질 때 마다 정사각형은 4개로 쪼개지고, 더 이상 쪼개지지 않을 때 까지 재귀 프로세스는 계속 진행 된다. 재귀 프로세스가 진행될 때는 첫번재 좌표부터 진행되기 때문에 매개변수로 넘겨줄 값은 좌표값 row, col와 정사각형 한변의 길이 N이다.

 

그림을 그리고 보니 왠지 화투같다,,

 

분할정복 방법에서 재귀 메소드는 다음 3가지 규칙을 가지게 된다.

 

1. 1과 0 중에서 동일한 값을 가진 정사각형인가? return  true || false

2. 동일하다면 정사각형의 숫자는 1과 0중 어떤 값인가? 

3. 재귀가 시작될 첫번째 지점의 좌표와 정사각형 N의 크기는 얼마인가?

 

 

분할정복 문제 중  백준 2630번 색종이 문제 알고리즘은 입력값이 공백이 포함된 숫자값이 였지만 백준 1992번 쿼드트리 알고리즘은 공백이 없는 숫자가 입력값으로 주어진다. String 클래스에서 charAt() 메소드를 이용해서 특정 위치의 값을 파싱하는 작업을 따로 거친다. 

 

JAVA CODE

/*
    Owner : Developer Blog
    Title : 쿼드트리
    Algorithm : 분할정복 알고리즘
    Date : 2022-03-01
*/

import java.util.*;

public class A_1992 {
    public static StringBuilder sb = new StringBuilder();
    public static int[][] quadArr;
    public static void main(String[] args){
    
        Scanner in =  new Scanner(System.in);
        int N = in.nextInt();
            
        quadArr = new int[N][N];

        for(int i=0; i<N; i++){
            String str = in.next();
            for(int j=0; j<N; j++){
                quadArr[i][j] = str.charAt(j)- '0';
            }
        }
        compression(0,0,N);
        System.out.println(sb);
    }
    // 숫자를 검증하는 메소드
    public static boolean checkNumber(int row, int col, int N){
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(quadArr[row][col] != quadArr[i+row][j+col]) return false;
            }
        }
        return true;
    }
    // 숫자를 판별하는 메소드
    public static void checkColor(int row, int col){
        if(quadArr[row][col]==0){
            sb.append(0);
        }else{
            sb.append(1);
        }
    }
    // 분할정복 메소드
    public static void compression(int row, int col, int N){
        
        if(checkNumber(row, col, N)){
            checkColor(row, col);
            
        }else{
            sb.append("(");
            compression(row, col, N/2);
            compression(row, col+N/2, N/2);
            compression(row+N/2, col, N/2);
            compression(row+N/2, col+N/2, N/2);
            sb.append(")");
            
        }   
        
        return;
    }
}

 

 

백준 1992 쿼드트리 알고리즘 결과 

224ms, 17MB 메모리를 사용해서 맞았습니다!