백준 알고리즘 2630번 분할정복 색종이 만들기 자바 JAVA

 

 

 

 

백준 알고리즘 2630번 문제는 분할 정복 방법으로 풀어보는 알고리즘이다. 분할정복(Divide and Conquer) 알고리즘은 큰 문제 자체로 해결할 수 없는 문제를 효율적으로 문제를 풀 수 있는 작은 단위로 나누는 하향식(Top-Down) 방식이다. 작은 단위에서 얻은 결과값을 합쳐서 전체 문제의 값을 구해내게 된다. 

 

분할 정복법 알고리즘을 구현하는 방법은 일반적으로 재귀 호출 방식을 사용한다. 하지만 재귀방식의 경우 오버헤드 문제(결과값을 얻기 위한 시간, 메모리 등 자원사용이 지나치게 많이 소요되는 문제)가 발생되기 때문에, 스택 혹은 큐 자료구조로 풀어내는 경우가 있다.

 

 

입력값으로 주어지는 N은 N*N으로 구성된 정사각형을 만들게 된다. N=2k, k는 1 이상 7 이하의 자연수로 2,4,8,16,32,64,128 중 하나가 주어지게 된다.

 

색종이를 쪼개는 방법은 2의 지수승으로 구성된 정사각형에 들어있는 숫자가 모두 동일하지 않으면 N/2 * N/2 색종이로 자르게 된다. 이 과정이 반복 되면서 전체 정사각형의 색종이를 자르는 방법이다.

 

 

 

풀이과정

 

풀이 방법은 분할 정복 방법으로 N/2로 정사각형을 쪼개면서 반복된다. 한번 정사각형이 분할 될 때 마다 재귀 함수는 1사분면, 2사분면 3사분면, 4사분면 총 4개의 콜백함수가 만들어져야 한다. 색종이 만들기의 핵심인 재귀함수의 로직을 정리하면 다음과 같다.

 

1. 입력값을 받아온다. Scanner 클래스 사용

2. N개의 정사각형의 값이 동일한지 파악하는 로직

3. 흰색/파랑색 색종이 카운터 ++;

4. 4개 분면의 재귀함수 호출

5. 최종 흰색/파랑색 색종이 카운터 출력

 

 

JAVA Code

/*
    Owner : Developer Blog
    Title : 색종이 만들기
    Algorithm : 분할정복 알고리즘
    Date : 2022-02-28
*/

import java.util.*;

public class A_2630 {
	// 전역 변수
    public static int[][] rectangle;
    public static int bluePaperCounter=0;
    public static int whitePaperCounter=0;
    
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();

        rectangle = new int[N][N];

        // 1. 입력값 Scanner 이용
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                rectangle[i][j] = in.nextInt();
            }
        }
        // 가로*세로 N 정사각형 값이 동일한지 확인
        reSize(0,0,N);      
        
        System.out.println(whitePaperCounter);
        System.out.println(bluePaperCounter);
    }
    
    // 구역 나누기
    public static void reSize(int row, int col, int N){
        if(checkColor(row, col, N)){
            paperCounter(row, col);
            return;
        }else{
        
        	// 4분면 분할
            reSize(row, col, N/2);
            reSize(row+N/2, col, N/2);
            reSize(row, col+N/2, N/2);
            reSize(row+N/2, col+N/2, N/2);          
        }
    }
    
    // 1과 0 동일 값 검색
    public static Boolean checkColor(int row, int col, int X){
        for(int i=row; i<row+X; i++){
            for(int j=col; j<col+X; j++){
                if(rectangle[row][col]!=rectangle[i][j]) return false;
            }
        }
        return true;
    }

	// 색종이 색깔 검색
    public static void paperCounter(int row, int col){
        switch(rectangle[row][col]){
            case 1:
                bluePaperCounter++;
                break;
            case 0:
                whitePaperCounter++;
                break;
        }
    }    
}

 

메모리를 3.4MB나 잡아먹었다. 시간은 428ms로 맞았습니다!