[백준] 2630번 - 색종이 만들기

 

2630번: 색종이 만들기

 

 

 

분할정복의 기본 개념을 이해하기 좋은 간단한 문제이다. 

 

분할정복(Divide And Conquer)이란 해결하고자 하는 문제를 작은 관점에서 해결하여 최종적으로 원래 해결하고자 했던 문제를 정복하는 방법이다.

 

이번 문제에서 주어진 조건을 살펴보자. 입력으로 주어지는 전체 정사각형에는 흰색 또는 파란색 두가지 색이 정사각형 모양으로 칠해져 있다. 여기서 '만약 전체 종이가 모두 같은 색으로 칠해져 있지 않다면 가로와 세로로 중간 부분을 자른다' 는 부분에 주목해보자. 이 말은 즉, 작은 색종이 조각이 될 수 있는 크기는 처음 입력으로 주어진 N을 2로 n번 나눈 크기이다.

따라서 자른 이후의 정사각형 모양의 색종이 조각이 가질 수 있는 한 변의 크기는 1, 2, 4, 8, ..., N 이다.

 

정답을 찾기위해서는 다음과 같은 과정을 거친다.

 

i) 처음 입력으로 주어진 색종이를 이중 배열에 담는다.

ii) 맨 왼쪽 위의 1x1 크기 구획의 색상이 나머지 전체 1x1 크기 구획의 색상과 일치하는지 확인한다.

iii-i) 만약 ii)에서 모든 구획의 색상이 일치한다면 해당 색상의 갯수를 1 증가시킨다.

iii-ii) 만약 ii)에서 색상이 일치하지 않는 구획이 존재한다면 색종이를 4사분면으로 나누어 ii) ~ iii) 을 반복한다.

 

 

 

전체 코드

import java.util.*;
import java.io.*;

public class Main {
    
    static int type = 2;
    static int white = 0;
    static int blue = 1;
    static int[] count;
    static int[][] board;
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int N = Integer.parseInt(br.readLine());
        
        board = new int[N][N];
        count = new int[type];
        
        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            
            for (int j=0; j<N; j++) board[i][j] = Integer.parseInt(st.nextToken());
        }
        
        dac(N, 0, 0);
        
        System.out.println(count[white] + "\n" + count[blue]);
        
        br.close();
    }
    
    static void dac (int size, int y, int x) {
        
        int color = board[y][x];
        
        if (colorCheck(size, y, x)) {
            count[color]++;
            return;
        }
        
        for (int i=y; i<y+size; i+=size/2) {
            for (int j=x; j<x+size; j+=size/2) 
                dac(size/2, i, j);
        }
    }
    
    static boolean colorCheck (int size, int y, int x) {
        
        int color = board[y][x];
        
        for (int i=y; i<y+size; i++) {
            for (int j=x; j<x+size; j++) {
                if (color != board[i][j]) return false;
            }
        }
        
        return true;
    }
}