CT | 백준 1780번 종이의 개수

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

import java.util.Scanner;

public class Main {

    static int countMinus1 = 0;
    static int count0 = 0;
    static int count1 = 0;

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

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

        divideAndConquer(matrix, 0, 0, n);

        System.out.println(countMinus1);
        System.out.println(count0);
        System.out.println(count1);

    }

    public static boolean checkSame(int[][] matrix, int x, int y, int size) {
        int firstValue = matrix[x][y];

        for(int i = x; i < x + size; i++) {
            for(int j = y; j < y + size; j++) {
                if(matrix[i][j] != firstValue) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void divideAndConquer(int[][] matrix, int x, int y, int size) {
        if(checkSame(matrix, x, y, size)) {
            if(matrix[x][y] == -1) {
                countMinus1++;
            } else if(matrix[x][y] == 0) {
                count0++;
            } else {
                count1++;
            }
        } else {
            int newSize = size / 3;
            for(int i = 0; i < 3; i++) {
                for(int j = 0; j < 3; j++) {
                    divideAndConquer(matrix, x + j * newSize, y + i * newSize, newSize);
                }
            }
        }
    }
}

 

코드 구조 및 설명

1. 카운트 변수 선언

static으로 처음에 선언된 3가지 변수들은 클래스 내 모든 메서드에서 이 변수들을 접근하기 쉽게 설정합니다.

 

2. main 메서드 

처음에 행렬의 크기와 값을 입력받고, divideAndConquer 메서드를 호출해 문제 해결을 시작합니다. 

마지막엔 종이의 개수를 순차적으로 출력합니다. 

 

3. checkSame 메서드 

주어진 부분 행렬이 모두 같은 숫자로 이루어졌는지 확인합니다. 

첫번째 값과 나머지 값들을 비교해 다르면 false, 모두 같으면 true를 return 합니다. 

이 메서드는 분할할지 멈출지를 결정하는 역할을 합니다.

 

4. divideAndConquer 메서드 

checkSame함수를 호출하여, 부분 행렬이 동일한 숫자로 이루어졌는지를 확인합니다. 

만약 모두 같다면 해당 숫자에 따라 카운트를 증가합니다. 

그렇지 않으면 행렬을 3 x 3 크기로 분할하고 각 작은 부분 행렬에 대해 divideAndConquer를 재귀적으로 호출합니다.