[분할정복 / 정올 ] 1335 : 색종이 만들기

[원리]

분할정복은 문제를 나눌 수 없을 때까지 나누어 병합하며 문제를 해결하는 방식

[분석]

이 문제를 풀수 있는 방법은 아래와 같이 2가지다.

-방법 1

현재 범위의 종이가 색깔을 본다.

1) white인가 -> whiteCount ++

2) black인가 -> blackCount ++

3) 둘다 아닌가 -> 분할해서 찾아본다.

사실 분할 정복알고리즘으로 대표적인 알고리즘은 Merge Sort인데, 이 경우 정말 최소단위까지 내려가 병합하여 정렬하지만, 내 소스의 경우 Merge Sort라고 하면 이미 정렬되어있는지 먼저 검사하고 분할하여 탐색한다고 볼 수 있다.

-방법 2

1) 일단 4분할을 한다.

2) 4분할 하여 반환된 색깔이 모두 같은 색인가?

2-True) 색을 반환한다.

2-False) 반환된 색깔들은 더이상 다른 곳에 병합될 수 없으므로 각 색깔에 대해 카운트한다.

방법2의경우 미리 검사하지 않고 정말 최소단위까지 분할 후 병합하며 해답을 찾아낸다.

[구현 | 방법 1]

import java.util.Scanner;
 
/**
 * @title 색종이 만들기
 * @problem http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=614&sca=3060
 * @author Jinseoung Lee
 * @type Divide And Conquer
 */
public class ColorPaper {
    public static Scanner sc;
    public static final boolean BLACK = true, WHITE = false;
    public static boolean[][] map;
    public static int N, whiteCount, blackCount;
    
    public static void main(String[] args) {
        sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new boolean[N][N];
        
        /***********************************************************************************
         * 입력
         ***********************************************************************************/
        for(int i = 0; i < N; i++){
            for(int j = 0 ; j < N ; j++){
                map[i][j] = sc.nextInt() == 1;
            }
        }
        
        /***********************************************************************************
         * 탐색
         ***********************************************************************************/
        search(0,0,N);
        
        
        /***********************************************************************************
         * 출력
         ***********************************************************************************/
        System.out.println(whiteCount);
        System.out.println(blackCount);
    }
    
    
    /**
     * 분할정복을 제귀적으로 탐색함
     * 
     * @param x        | 시작 x 좌표
     * @param y        | 시작 y 좌표
     * @param range    | 검색 범위
     */
    public static void search (int x, int y, int range){
        
        // 이 영역이 BLACK이나 WHITE도 아닐 때
        if(!is(ColorPaper.BLACK, x, y, range) && !is(ColorPaper.WHITE, x, y, range) ){
            int increase = range/2;
            search(x, y, increase);
            search(x+increase, y, increase);
            search(x, y+increase, increase);
            search(x+increase, y+increase, increase);
        }
    }
    
    
    /**
     * 이 영역이 white인지 black인지 아니면 mixed 인지 검색
     * 
     * @param TYPE    | Main.WHITE, Main.BLACK 을통해 이것이 화이트 또는 블랙인지를 찾을 수 있음
     * @param x        | 시작 X좌표
     * @param y        | 시작 Y좌표
     * @param range    | 검색 범위
     * @return        | false, true에 따라서 맞는지 아닌지에 대해서 반환
     * 
     * @example
     * is(Main.BLACK, 0, 0, N) -> 0, 0부터 N만큼 체크하며 BLACK인지를 판단한다.
     */
    public static boolean is (boolean TYPE, int x, int y, int range){
        for(int i = y; i < y+range; i++){
            for(int j = x; j < x+range; j++){
                if(map[i][j] != TYPE) return false;
            }
        }
        if(TYPE == BLACK) blackCount++;
        else if(TYPE == WHITE) whiteCount++;
        return true;
    }
}

[구현 | 방법 2 - 재귀 | 분할 -> 병합 순으로 진행되며 병합하는 과정에서 해답을 도출해낸다. ]

public class ColorPaperReal {
    public static Scanner sc;
    public static int[] counts = new int[3];
    public static int[][] map;
    public static int N;
    
    public static void main(String[] args) {
        sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new int[N][N];
        
        /***********************************************************************************
         * 입력
         ***********************************************************************************/
        for(int i = 0; i < N; i++){
            for(int j = 0 ; j < N ; j++){
                map[i][j] = sc.nextInt();
            }
        }
        
        /***********************************************************************************
         * 탐색
         ***********************************************************************************/
        counts[search(0,0,N)]++;
        
        /***********************************************************************************
         * 출력
         ***********************************************************************************/
        System.out.println(counts[0]);
        System.out.println(counts[1]);
    }
    
    public static int search ( int x, int y, int range){
        if(range == 1 ) return map[y][x];
        
        int[] results = new int[4];
        int increase = range/2;
        results[0] = search(x, y, increase);
        results[1] = search(x+increase, y, increase);
        results[2] = search(x, y+increase, increase);
        results[3] = search(x+increase, y+increase, increase);
        
        if(!isAllEquals(results)){
            for(int i = 0 ; i < results.length; i ++)
                counts[results[i]]++;
            return 2; 
        } else {
            return results[0];
        }
    }
    public static boolean isAllEquals(int[] results){
        int target = results[0];
        for(int i = 1; i < results.length; i++){
            if(target != results[i]) return false;
        }
        return true;
    }
}
 

[구현 | 방법 2 - 포문 구현 | 분할하는 과정이 없고 병합하며 해답을 도출해 낸다. ]

public class ColorPaperFast {
    public static Scanner sc;
    public static int[] counts = new int[3];
    public static byte[][] map;
    public static int N;
    
    public static void main(String[] args) {
        sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new byte[N][N];
        /***********************************************************************************
         * 입력
         ***********************************************************************************/
        for(int i = 0; i < N; i++){
            for(int j = 0 ; j < N ; j++){
                map[i][j] = (byte)sc.nextInt();
            }
        }
        /***********************************************************************************
         * 탐색
         ***********************************************************************************/
        for(int i = N; i > 1; i/=2 ){
            int mixedCount = 0;
            for(int y = 0; y < i; y += 2){
                for(int x = 0; x < i; x += 2){
                    if(!(map[y][x] == map[y][x+1] && map[y][x+1] == map[y+1][x] && map[y+1][x] == map[y+1][x+1] )){
                        counts[map[y][x]]++;
                        counts[map[y][x+1]]++;
                        counts[map[y+1][x]]++;
                        counts[map[y+1][x+1]]++;
                        map[y/2][x/2] = 2;
                        mixedCount++;
                    } else {
                        map[y/2][x/2] = map[y][x];
                    }
                }
            }
            if(mixedCount == (N*N)/4 ) break;
        }
        /***********************************************************************************
         * 출력
         ***********************************************************************************/
        System.out.println(counts[0]);
        System.out.println(counts[1]);
    }
}