[백준] 2630 : 색종이 만들기 JAVA 풀이

 

이전에 풀었던 쿼드트리 문제와 푸는 방식은 동일하다.

한 종이가 파란색 또는 흰색 둘 중 하나의 색으로만 이루어져있다면

그 색으로만 이루어진 종이의 수를 증가시킨다.

종이가 하나의 색으로 이루어져있지 않다면 그 종이를 같은 크기로 4분할을 하고 위 과정을 반복하면 된다.

 

1. n을 입력받는다.

2. 종이에 각 칸이 어떤 색인지 저장할 2차원 배열 arr[n][n]를 생성한다

3. arr에 입력받은 값을 저장한다.

4. 흰색 종이의 개수와 파란색 종이의 개수를 저장할 배열 cnt[2]를 생성한다.

5. 종이가 하나의 색으로만으로 이루어져있는지 확인하는 함수 colorCheck를 구현한다.

    종이의 첫번째 칸을 color라는 변수에 저장하고, 그 종이의 모든 칸이 color와 같은지 체크한다.

    color와 색이 다른 칸이 있다면 -1을 반환한다.

    종이가 흰색으로만 이루어져있으면 0을 반환한다.

    종이가 파란색으로만 이루어져있으면 1을 반환한다.

6. 종이를 4분할을 하는 함수 partition을 구현한다.

    colorCheck함수로 종이가 하나의 색으로만 이루어져있는지 확인한다.

    colorCheck함수의 반환값이 -1이면(다른 색이 섞여있다면)

    그 종이를 4분할해 partition함수를 재귀호출한다.

    0이거나 1이면 이에 따라 cnt[0]나 cnt[1]의 값을 증가시켜 흰색, 파란색 종이의 개수를 센다.

7. cnt[0]과 cnt[1]을 출력한다.

 

import java.io.*;
import java.util.*;
public class Main{
    static int arr[][];
    static int[] cnt = new int[2];
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        arr = new int[n][n];
        
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0;j<n;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        partition(0,0,n);
        System.out.println(cnt[0]);
        System.out.println(cnt[1]);
    }
    static void partition(int x, int y, int size){
        if(colorCheck(x,y,size)==0){
            cnt[0]++;
        }else if(colorCheck(x,y,size)==1){
            cnt[1]++;
        }
        else{
            int newsize = size/2;
            partition(x,y,newsize);
            partition(x,y+newsize,newsize);
            partition(x+newsize,y,newsize);
            partition(x+newsize,y+newsize,newsize);
        }
    }
    static int colorCheck(int x, int y, int size){
        int color = arr[x][y];
        for(int i=x;i<x+size;i++){
            for(int j=y;j<y+size;j++){
                if(color!=arr[i][j]) return -1;
            }
        }
        if(color ==0) return 0;
        else return 1;
    }
}