[BOJ/백준] 1780 종이의 개수 (S2)

문제

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

풀이

색종이의 수가 모두 같은 수라면 이 색종이를 그대로 사용하지만 좌측의 그림과 같이 모두 같은 수가 아니라면 우측 그림처럼 9등분을 한다.

현재는 row와 column 모두 9이므로 9등분을 하면 나눠진 색종이의 size는 이전의 size/3이 되어 3이 된다.

나누어진 색종이를 좌표로 표현해보면 위와 같이 표현할 수 있다.

N이 9 일 때의 결과를 보면 위 그림과 같이 나오는 것을 알 수 있다.

Code

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int [][] arr;
    static int [] answer = new int[3];  // -1, 0, 1


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        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());
            }
        }

        cut(0, 0, N);
        for (int i = 0; i < 3; i++) {
            bw.write(answer[i] + "\n");
        }
        bw.flush();
        bw.close();
    }

    public static void cut(int x, int y, int size) {
        // 다 같은 숫자면 더하기
        if (numCheck(x, y, size)) {
            if (arr[x][y] == -1) {
                answer[0]++;
            } else if (arr[x][y] == 0) {
                answer[1]++;
            } else {
                answer[2]++;
            }
        } else {  // check가 false면? (다른 숫자가 포함되어 있으면) ->  9분할 진행
            int newSize = size / 3;

            // 왼쪽 위부터 오른쪽 아래로 cut()를 진행하며 분할을 진행
            cut(x, y, newSize);  // 1
            cut(x, y + newSize, newSize);  // 2
            cut(x, y + newSize * 2, newSize);  // 3

            cut(x + newSize, y, newSize);  // 4
            cut(x + newSize, y + newSize, newSize);  // 5
            cut(x + newSize, y + newSize * 2, newSize);  // 6

            cut(x + newSize * 2, y, newSize);  // 7
            cut(x + newSize * 2, y + newSize, newSize);  // 8
            cut(x + newSize * 2, y + newSize * 2, newSize);  // 9
        }
    }

    public static boolean numCheck(int x, int y, int size) {
        int start = arr[x][y];
        boolean check = true;
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                // start(시작점)와 각 칸에 표기된 수를 비교하여 다르면 false를 반환
                if (start != arr[i][j]) {
                    check = false;
                    break;
                }
            }
        }
        return check;
    }
}