백준 1780번 : 종이의 개수 (Java)

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

1780번: 종이의 개수

---

[풀이]

• '쿼드 트리' 방식을 이용하여 풀 수 있는 문제입니다.(이전에 4개의 공간으로 분할해서 푸는 문제를 의미하여 쿼드트리이지만 이번에는 9개로 분할해서 푸는 문제입니다.)
• N은 3의 제곱수 이기 때문에 계속 9개로 분리를 할 수 있으며 최종적으로는 1개로 분리가 됩니다.
• 9개의 영역으로 나누어야 하기 때문에 각 나눠진 것은 원래 크기의 3분의 1 크기로 감소합니다.
• check() 메소드를 통해 2차원 배열 내부에 다른 원소들이 있을 경우 false를 반환하며, 같을 경우 true를 반환합니다.
• check() 메소드를 통해 true가 반환될 경우, one, zero, minusOne 변수 각각 개수를 세면 됩니다.

---

[코드]

 

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

public class Main {
    static int N;
    static int[][] arr;
    static int zero, one, minusOne;

    public static boolean check(int x, int y, int len) {
        int value = arr[x][y];

        for (int i = x; i < x + len; i++) {
            for (int j = y; j < y + len; j++) {
                if (value != arr[i][j])
                    return false;
            }
        }
        return true;
    }

    public static void solve(int x, int y, int len) {
        if (check(x, y, len)) {
            if (arr[x][y] == -1) minusOne += 1;
            else if (arr[x][y] == 0) zero += 1;
            else one += 1;
            return;
        }

        int tempLen = len / 3;

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                solve(x + i * tempLen, y + j * tempLen, tempLen);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        solve(0, 0, N);
        System.out.println(minusOne);
        System.out.println(zero);
        System.out.println(one);
    }
}