[BOJ_2630] 색종이 만들기

설명

---

말 그대로 1사분면 2사분면 3사분면 4사분면을 나눠서 정복하는 방법입니다.

 

재귀 함수를 사용하기 때문에 적절히 리턴 코드를 의식해서 코드를 짜면 되고 사각형 탐색 시 모든 컬러가 같은 경우가 아닌 사각형을 탐색 했을때는 그 사각형의 내부를 탐색하는 식으로 코드를 작성하면 됩니다.

 

코드

---

package BOJ.Divide;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_2630 {
    static int black = 0;
    static int white = 0;
    static int[][] map;
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");
        int N = Integer.parseInt(tk.nextToken());

        map = new int[N][N];

        for (int i = 0; i < N; i++){
            tk = new StringTokenizer(in.readLine()," ");
            for (int j = 0; j < N; j++){
                map[i][j] = Integer.parseInt(tk.nextToken());
            }
        }
        div(0,0,N);
        System.out.println(white);
        System.out.println(black);
    }

    private static void div(int row, int col, int size) {
        boolean checker = true;
        int color = map[row][col];
        for (int i = row; i < row + size; i++){
            for (int j = col; j < col + size; j++){
                if(color != map[i][j])
                {
                    checker = false;
                    break;
                }
            }
        }
        if(size == 1){
            if(map[row][col] == 1){
                black++;
            }else{
                white++;
            }
            return;
        }
        if(color == 1 && checker) {
            black++;
        }else if(color == 0 && checker) {
            white++;
        }else {
            div(row, col, (size / 2));
            div(row, col + (size / 2), (size / 2));
            div(row + (size / 2), col, (size / 2));
            div(row + (size / 2), col + (size / 2), (size / 2));
        }
    }
}

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