BOJ02630 색종이 만들기

https://www.acmicpc.net/problem/2630 (opens new window)

여러 개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀식 또는 파란색 종이를 만든다.

분할 정복

분할 정복 알고리즘은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다.

위 문제의 경우 큰 종이를 사분면을 기준으로 4개로 나눠가며 분할 정복한다. 만약 해당 나눈 사분면이 모두 같은 색이면 잘라야 하기 때문에 분할을 더 진행하지 않도록 한다.

private static void partition(int row, int col, int size) {

    if (isSameColor(row, col, size)) {
        if (board[row][col] == 0) {
            white++;
        } else if (board[row][col] == 1) {
            blue++;
        }
        return;
    }

    int halfSize = size / 2;
    partition(row, col + halfSize, halfSize); // 1사분면
    partition(row, col, halfSize); // 2사분면
    partition(row + halfSize, col, halfSize); // 3사분면
    partition(row + halfSize, col + halfSize, halfSize); // 4사분면
}

제출 코드

아래는 최종 제출 코드이다.

import java.util.Scanner;

public class BOJ2630 {

    private static int white, blue;
    private static int[][] board;

    private static void partition(int row, int col, int size) {

        if (isSameColor(row, col, size)) {
            if (board[row][col] == 0) {
                white++;
            } else if (board[row][col] == 1) {
                blue++;
            }
            return;
        }

        int halfSize = size / 2;
        partition(row, col + halfSize, halfSize); // 1사분면
        partition(row, col, halfSize); // 2사분면
        partition(row + halfSize, col, halfSize); // 3사분면
        partition(row + halfSize, col + halfSize, halfSize); // 4사분면
    }

    private static boolean isSameColor(int row, int col, int size) {

        int color = board[row][col]; // color 기준

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

        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        board = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = scanner.nextInt();
            }
        }

        partition(0, 0, n);

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

#algorithm #BOJ #분할 정복 #재귀