📖 [백준알고리즘 풀이] Q.1780 종이의 개수 문제 풀이 - java

📖 문제

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

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

만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

🔍 접근법

Q.1780 종이의 개수 문제입니다.

Q.1992 쿼드트리 문제와 비슷한 문제입니다.

문제에 주어진 조건을 잘 살펴보면 쉽게 풀이가 가능합니다.

N * N 크기의 종이 행렬이 주어집니다. 이 종이의 각 칸에는 -1 , 0 , 1의 세 값 중 하나가 저장되어 있는데

이 종이들을 적절한 크기로 자르려고 합니다.

이 때 종이가 모두 같은 수가 되어있을때 이 종이를 그대로 사용하려고 합니다.

종이가 모두 같은 수가 아니라면 같은 크기로 9개의 종이를 자르고 다시 같은 수로 이루어져있는지를

확인하기를 반복하면 됩니다.

똑같은 크기로 계속 분할하며 확인하므로

분할정복 알고리즘을 통해 풀이가 가능합니다.

문제 그대로 종이가 같은 수가 아니라면 9등분으로 나누고 종이가 같은 수인지 아닌지 확인하는 과정을 반복하면

답을 도출해낼 수 있습니다.

이 과정을 반복하며 모든 숫자가 0인 경우, 1인 경우 , -1인 경우를 모두 구하면 됩니다.

💻 코드

package problem.divide_conquer;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main_1780 {
    static int n;
    static int paper[][];
    static int minusOne = 0;
    static int zero = 0;
    static int plusOne = 0;

    public static void main(String[] args) throws IOException {
        input();
        solve(0, 0, n);
        System.out.println(minusOne);
        System.out.println(zero);
        System.out.println(plusOne);
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        paper = new int[n][n];
        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                paper[i][j] = Integer.parseInt(input[j]);
            }
        }

        br.close();
    }

    private static void solve(int startX, int startY, int len) {
        if (check(startX, startY, len)) {
            if (paper[startY][startX] == 1) {
                plusOne++;
            } else if (paper[startY][startX] == 0) {
                zero++;
            } else {
                minusOne++;
            }
        } else {

            int length = len / 3;
            solve(startX, startY, length);
            solve(startX, startY + length, length);
            solve(startX, startY + (2 * length), length);

            solve(startX + length, startY, length);
            solve(startX + length, startY + length, length);
            solve(startX + length, startY + (2 * length), length);

            solve(startX + (2 * length), startY, length);
            solve(startX + (2 * length), startY + length, length);
            solve(startX + (2 * length), startY + (2 * length), length);
        }
    }

    public static boolean check(int startX, int startY, int len) {
        int number = paper[startY][startX];
        for (int i = startY; i < startY + len; i++) {
            for (int j = startX; j < startX + len; j++) {

                if (number != paper[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}

Written on May 3, 2021