백준 2630 색종이 만들기 <S2> - 재귀, 분할 정복

문제가 길다.

정리하면 1과 0으로 나뉘어진 정사각형의 색종이가 주어지고, N/2로 나누면서 정사각형이 모두 한 색인 경우 정복이 끝난경우이다. 전부 나눈 후 나뉘어진 파란색 1 과 하얀색 0의 개수를 출력하면 된다.

 

입력된 종이는 이차원 배열로 받아주고, 재귀함수를 쓰기위해 div 함수를 선언했다.

if( (paper[x][y] - paper[x+i][y+j]) != 0 ) 를 통해서 같은 숫자끼리 영역에 존재하는지 확인했고,

boolean chk 를 통해서 영역내에 다른 색상이 있는지 판단하여 존재할 시 재귀함수를 호출했다.

범위는 4등분하여 x, y, n을 다시 재귀함수에 넣어줬다.

 

import java.util.*;
import java.util.Scanner;
 
 
public class Main {
    
        static int [][] paper ;
        static int blue = 0;
        static int white = 0;
        
    public static void main(String[] args) {
        // Input
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        paper = new int[N][N];
        
        for(int i = 0; i<paper.length; i++) {
            for(int j = 0 ; j<paper[i].length; j++) {
                paper[i][j] = sc.nextInt();
            }
        }
 
       
        //output
        div(0,0,N); 
        System.out.println(white);
        System.out.println(blue);
        
    }
    //logic
    public static void div(int x,int y, int n) { //x,y,범위 넣어주기
        // 범위 내의 다른 색이 있는지 체크
        boolean chk = true;
        for(int i =0; i<n ; i++) {
            for(int j = 0; j<n; j++) {
                // 한 종류의 색상만 있는지 체크. 
                if( (paper[x][y] - paper[x+i][y+j]) != 0 ) {
                    chk = false;
                    break;
                }
                if(chk == false) {
                    break;
                }
            }
        }
        
        if(chk) {
            if(paper[x][y] == 0) {
                white ++;
            }else {
                blue ++;
            }
        }else {
            // 4등분하여 재귀함수 호출
            div(x + n/2, y, n/2);
            div(x,y,n/2);
            div(x + n/2, y + n/2, n/2);
            div(x, y + n/2, n/2);
        }
        
        
        
    }
}
 
//n의 길이에서 쪼개면 n/2
//(x + n/2, y) (x,y) / (x+n/2,y+n/2) / (x,y+ n/2) 4가지로 재귀