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

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

문제

---

풀이

주어진 정사각형을 계속 4분할 해야하므로 분할 정복을 활용해야 한다

1. 색종이가 모두 같은 색이면 더 이상 자르지 않고 총 개수를 구한다
2. 다른 색이라면 (현재 사이즈 / 2)로 4등분한다
3. 1, 2를 재귀적으로 호출한다

코드

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

public class Main {

    static int[][] arr;
    static int blue = 0;
    static int white = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        // 색종이 정보 입력
        int N = Integer.parseInt(br.readLine());
        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(white);
        System.out.println(blue);

        br.close();
    }

    static void partition(int row, int col, int size) {
        // 현재 영역이 모두 같은 색인지 확인
        if (colorCheck(row, col, size)) {
            // 배열 값이 0이면 흰색이므로 흰색 +1
            if (arr[row][col] == 0) {
                white++;
            } else {
                // 배열 값이 1이면 파란색이므로 흰색 +1
                blue++;
            }
            // 같은 색이므로 더 이상 분할하지 않고 재귀 종료
            return;
        }

        // 색이 섞여있다면 4분할
        int newSize = size / 2;
        partition(row, col, newSize);   // part 1
        partition(row, col + newSize, newSize); // part 2
        partition(row + newSize, col, newSize); // part 3
        partition(row + newSize, col + newSize, newSize); // part 4
    }

    // 현재 영역에 색깔이 모두 같은지 확인하는 메서드
    static boolean colorCheck(int row, int col, int size) {
        // 첫번째 색깔
        int color = arr[row][col];
        for (int i = row; i < row + size; i++) {
            for (int j = col; j < col + size; j++) {
                // 다른 색깔이 나온다면 false 리턴
                if (color != arr[i][j]) {
                    return false;
                }
            }
        }
        // 다 같은 색이면 true 리턴
        return true;
    }
}

결과