[백준/1992] 쿼드트리 (실버 1) JAVA

1. 처음 주어진 전체 맵이 모두 0이거나 1이면 바로 끝남.
2. 맵의 모든 요소가 동일하지 않을 경우 4개로 나눔(4등분)
3. 나누어서 1~2 절차 반복(재귀). 재귀 순서는 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서주어짐
4. 탈출조건 : 2차원 배열 요소 1개 or 2차원 배열 전체 요소 통일
5. 반환특성 : 4개가 나누어질때 괄호로 묶어야함.

package task.silver.qaudtree1992;

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

public class Main {

    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N;
    static List<List<Integer>> map;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        map = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        map();
        quadTree(map);

        bw.flush();
        br.close();
        bw.close();
    }

    private static void map() throws IOException {
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String[] split = st.nextToken().split("");
            map.add(new ArrayList<>());
            for (int j = 0; j < N; j++) {
                map.get(i).add(Integer.parseInt(split[j]));
            }
        }
    }

    private static boolean checkSame(List<List<Integer>> subMap) {
        int size = subMap.size();
        int index = subMap.get(0).get(0);

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                Integer findValue = subMap.get(i).get(j);
                if (index != findValue) {
                    return false;
                }
            }
        }
        return true;
    }

    private static void quadTree(List<List<Integer>> map) throws IOException {
        if (checkSame(map)) {
            bw.write(Integer.toString(map.get(0).get(0)));
            return;
        } else {
            Deque<List<List<Integer>>> deque = mapSlice(map);
            bw.write("(");
            while (!deque.isEmpty()) {
                quadTree(deque.poll());
            }
            bw.write(")");
        }
    }

    private static Deque<List<List<Integer>>> mapSlice(List<List<Integer>> map) {
        Deque<List<List<Integer>>> deque = new ArrayDeque<>();

        int size = map.size();

        List<List<Integer>> leftUP = cut4(map, new int[] {0, size/2-1, 0, size/2-1});
        List<List<Integer>> rightUP = cut4(map, new int[] {0, size/2-1, size/2, size-1});
        List<List<Integer>> leftDown = cut4(map, new int[] {size/2, size-1, 0, size/2-1});
        List<List<Integer>> rightDown = cut4(map, new int[] {size/2, size-1, size/2, size-1});

        deque.offer(leftUP);
        deque.offer(rightUP);
        deque.offer(leftDown);
        deque.offer(rightDown);

        return deque;
    }

    private static List<List<Integer>> cut4(List<List<Integer>> map, int[] index) {
        List<List<Integer>> tmpSubMap = new ArrayList<>();
        int count = 0;

        for (int i = index[0]; i <= index[1]; i++) {
            tmpSubMap.add(new ArrayList<>());
            for (int j = index[2]; j <= index[3]; j++) {
                tmpSubMap.get(count).add(map.get(i).get(j));
            }
            count++;
        }

        return tmpSubMap;
    }
}