백준 2630번 ) 색종이 만들기 (java)

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

2630번: 색종이 만들기

 

문제

 

풀이

 

이 문제는 분할정복 문제였다. 재귀적으로 함수를 호출하면서 해당하는 영역이 모두 같은색인지 확인하는 방식으로 진행하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_2630 {

    public static int[][] paper;
    public static int white = 0;
    public static int blue = 0;

    public static void solution(int row, int col, int size){
        if(colorCheck(row, col, size)){
            if(paper[row][col] == 0) white++;
            else blue++;
            return;
        }

        int newSize = size / 2;
        solution(row, col, newSize);
        solution(row, col + newSize, newSize);
        solution(row + newSize, col, newSize);
        solution(row + newSize, col + newSize, newSize);
    }

    public static boolean colorCheck(int row, int col, int size){
        int color = paper[row][col];

        for(int i = row; i < row+size; i++) {
            for(int j = col; j < col+size; j++){
                if(paper[i][j] != color) return false;
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        paper = new int[N][N];

        StringTokenizer st;

        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine(), " ");

            for(int j = 0; j < N; j++){
                paper[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        solution(0, 0, N);

        System.out.println(white);
        System.out.println(blue);
    }
}

 

• main에서는 BufferedReader를 이용하여 배열을 읽어오고 저장한 후, solution 함수를 호출한다.
• solution 함수에서는 사이즈에 따른 영역만큼 해당하는 영역이 모두 같은 색으로 되어있는지 확인 후, colorCheck가 true라면 해당하는 색의 카운트를 올린다. 같은색으로 되어있지 않다면 영역을 2씩 나누어 다시 재귀적으로 solution 함수를 호출한다. (이는 N이 2의 제곱이라 가능함.)
• colorCheck 함수에서는 첫 타일의 색과 나머지 사이즈까지의 색이 같은지 비교하여 true 또는 false를 반환한다.

 

 

궁금한점

이것보다 효율적인 방법으로 풀 수 있을까??