BOJ01780 종이의 개수

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

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성한다.

분할 정복

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

탐색하는 범위에는 모든 종이가 같은 number를 가지고 있어야 한다. 아래는 그것을 판별하기 위한 메서드이다.

private static boolean isSameNumber(int row, int col, int size) {
    int number = board[row][col];

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

    return true;
}

이제 재귀적으로 분할하여 정복을 진행한다. 정복을 위한 구역이 모두 같은 숫자인 경우 더 이상 재귀를 진행하지 않도록 조정한다.

같은 숫자가 아니라면 같은 숫자를 가진 구역을 찾기 위해 분할하여 탐색을 진행한다.

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

    if (isSameNumber(row, col, size)) {
        if (board[row][col] == -1) {
            minus++;
        } else if (board[row][col] == 0) {
            zero++;
        } else {
            plus++;
        }

        return;
    }

    int halfSize = size / 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            partition(row + (i * halfSize), col + (j * halfSize), halfSize);
        }
    }
}

제출 코드

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

import java.util.Scanner;

public class BOJ1780 {

    private static int n;
    private static int[][] board;
    private static int minus, zero, plus;

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

        if (isSameNumber(row, col, size)) {
            if (board[row][col] == -1) {
                minus++;
            } else if (board[row][col] == 0) {
                zero++;
            } else {
                plus++;
            }

            return;
        }

        int halfSize = size / 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                partition(row + (i * halfSize), col + (j * halfSize), halfSize);
            }
        }
    }

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

        int number = board[row][col];

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

        return true;
    }

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

        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(minus);
        System.out.println(zero);
        System.out.println(plus);
    }
}

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