백준 1992 "쿼드트리" (JAVA)

🔍 문제링크

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

문제 요약

• N×N 크기의 영상(0과 1로 이루어진 행렬)이 주어짐.
• 같은 숫자로만 이루어진 영역을 하나로 압축하여 출력.
• 그렇지 않다면 영역을 4등분하여 압축을 재귀적으로 진행.
• 최종 결과를 쿼드트리(QuadTree) 형식으로 출력.

---

🛠 풀이 및 알고리즘

1. 분할 정복 (Divide & Conquer)
   • 현재 영역(N×N)이 모두 같은 숫자로 이루어졌는지 검사.
   • 다르면 4등분하여 재귀적으로 압축 진행.
2. 출력 형식
   • 압축된 영역이면 숫자(0 또는 1) 그대로 출력.
   • 분할된 경우 (왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래) 형태로 출력.
3. 시간 최적화
   • 같은 숫자로 이루어진 경우 즉시 반환하여 불필요한 탐색 최소화.
   • StringBuilder를 활용하여 문자열 연결 연산 최적화.

---

💡 코드

public class Baekjoon_1992 {
    static int n;
    static int[][] board;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        board = new int[n][n];
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            for (int j = 0; j < n; j++) {
                board[i][j] = s.charAt(j) - '0';
            }
        }
        // 맨 처음 체크
        if (isPossible(n, 0, 0)) {
            System.out.println(board[0][0]);
            return;
        }
        compress(n, 0, 0);
        System.out.println(sb);
    }

    static void compress(int n, int x, int y) {

        if (isPossible(n, x, y)) {
            sb.append(board[x][y]);
            return;
        }
        int mid = n / 2;
        sb.append("(");
        // 왼쪽 위
        compress(mid, x, y);
        // 오른쪽 위
        compress(mid, x, y + mid);
        // 왼쪽 아래
        compress(mid, x + mid, y);
        // 오른쪽 아래
        compress(mid, x + mid, y + mid);
        sb.append(")");
    }


    // 분할 하는지 확인
    static boolean isPossible(int n, int x, int y) {
        int num = board[x][y];
        for (int i = x; i < x + n; i++) {
            for (int j = y; j < y + n; j++) {
                // 색이 다르면 분할해야함
                if (num != board[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

}

---

🏆 시간 복잡도 분석

1. 최악의 경우 완전 분할(O(N log N))
   • N×N 크기의 행렬을 계속 4등분하므로, 깊이는 log N.
   • 각 깊이에서 O(N^2) 연산 수행 → 최악의 경우 O(N^2 log N).