[백준][JAVA]색종이 만들기(2630번) - 분할 정복

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

2630번: 색종이 만들기

* 문제는 해당 게시물 참고바랍니다.

 

분할 정복(Divide and Conquer)이란 재귀를 응용하는 알고리즘으로 여러 알고리즘의 기본이 되는 해결방법입니다.

기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념입니다.

 

분할 정복은 크게 3단계로 나눌 수 있습니다.

 

1. 원래 문제를 분할하여 비슷한 유형으로 작은 문제를 만듭니다.

2. 분할된 각각의 문제를 재귀적으로 해결합니다.

3. 분할하여 재귀적으로 해결한 문제들을 합하여 기존 문제의 답을 얻습니다.

 

이제 해당 문제를 해결한 코드를 보겠습니다.

import java.util.*;
public class Main {


    public static int[][] paper;
    public static int white = 0;
    public static int blue = 0;
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        paper = new int[n][n];

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                paper[i][j] = scanner.nextInt();
            }
        }

        cutPaper(0,0,n);
        System.out.println(white);
        System.out.println(blue);

    }

    public static void cutPaper(int ver, int hor, int size){

        if(checkColor(ver,hor,size)){
            return;
        } else {
            cutPaper(ver,hor,size/2);
            cutPaper(ver, hor+size/2,size/2);
            cutPaper(ver+size/2, hor, size/2);
            cutPaper(ver+size/2,hor+size/2,size/2);
        }
    }

    public static boolean checkColor(int ver, int hor, int size){

        int color = paper[ver][hor];   

        for(int i= ver; i< ver+size; i++){
            for(int j= hor; j<hor+size; j++){
                if(paper[i][j] != color) {
                    return false;
                }
            }
        }
        if(color == 0){
            white++;
        } else {
            blue++;
        }
        return true;


    }
}

 

결과