[Java]백준 1992번 :: 쿼드트리

백준 온라인 저지 1992번 '쿼드트리'

Java 알고리즘 문제풀이

풀이

이 문제는 분할정복(Divide and Conquer)로 풀면된다.

분할정복 사실은 정말 쉬운 개념이다.

복잡한 문제를 해결할 수 있는 작은 단위로 나누어 처리하고 이것을 합치면 된다.

이 문제를 풀면 백준 1780번 문제 종이의 개수도 아주 쉽게 풀 수 있을 것이다.

(유사한 문제 풀기 -> 백준 1780번 문제종이 https://developer-mac.tistory.com/38)

그리고 쿼드트리는 단순히 노드가 4개 있는 것이라고 생각하면 된다.

즉, 4개로 쪼개서 4개의 노드가 생겨난다고 생각하면 된다.

 

먼저 입력을 받은 후 divide 함수에서 재귀적으로 동작하고 if 문을 두어 모든 원소가 0이거나 1일때 빠져나오게 하면되는 문제다.

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

public class beak_1992 {
    private static int n, m;
    private static int map[][];

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine().trim());

        map = new int[n][n];
        int[] num = new int[n];

        for (int i = 0; i < n; i++) {
            String num_1 = br.readLine();
            for (int j = 0; j < n; j++) {
                num[j] = num_1.charAt(j);
                map[i][j] = (int)num[j] - 48;
            }
        }
        divide(0, 0, n);
    }

    private static boolean check(int row, int col, int n) {
        int std = map[row][col];
        for (int i = row; i < row + n; i++) {
            for (int j = col; j < col + n; j++) {
                if (std != map[i][j]) {
                    return false;
                }
            }
        }
        m = std;
        return true;
    }

    private static void divide(int row, int col, int n) {
        if (check(row, col, n)) {
            System.out.print(m);
        } else {
            System.out.print("(");
            int s = n / 2;
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 2; j++) {
                    divide(row + s * i, col + s * j, s);
                }
            }
            System.out.print(")");
        }
    }
}