[백준] 1992번 - 쿼드트리 풀이 및 코드 분석 (Java)

문제 링크

1. 문제 분석

쿼드트리는 흑백 영상 압축 방식 중 하나로, 2차원 배열을 네 개의 구역으로 나누어 표현하는 방법.

주어진 영상이 모두 같은 값(0 또는 1)으로 이루어져 있다면 해당 숫자로 압축되지만, 0과 1이 섞여 있다면 네 개의 부분으로 나눈 뒤 각 부분을 다시 압축하는 방식.

이 문제는 재귀적인 방식으로 2차원 배열을 압축하여 출력하는 것이 핵심.

입력 조건

• 첫 번째 줄: 영상의 크기 N (1 ≤ N ≤ 64), 항상 2의 제곱수로 주어짐
• 두 번째 줄부터: N개의 길이가 N인 문자열 (0 또는 1)

출력 조건

• 압축된 쿼드트리 결과를 출력

예를 들어, 아래와 같은 입력이 주어진다면:

8
11110000
11110000
00001111
00001111
11110000
11110000
00001111
00001111

출력은 다음과 같이 됩니다:

((1100)(1100)(0011)(0011))

2. 해결 방법

분할 정복 (Divide and Conquer)와 재귀 사용

1. 기저 조건
   • 주어진 영역이 1x1 크기일 경우, 해당 숫자를 출력.
   • 주어진 영역이 모두 같은 숫자(0 또는 1)로 이루어져 있다면, 해당 숫자로 압축.
2. 재귀적으로 4개의 영역으로 나누어 탐색
   • 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 영역을 재귀적으로 탐색.
   • 4개의 영역을 다시 같은 방식으로 처리하며 압축된 결과를 괄호로 묶어서 표현.
3. 압축된 결과 저장 및 출력
   • StringBuilder를 사용하여 문자열을 효율적으로 저장하고 출력.

3. 코드 구현

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

public class Main {

    static int N;
    static int[][] board;
    static StringBuilder sb = new StringBuilder();

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

        for (int r = 0; r < N; r++) {
            String[] arr = br.readLine().split("");
            for (int c = 0; c < N; c++) {
                board[r][c] = Integer.parseInt(arr[c]);
            }
        }

        compress(0, N, 0, N);
        System.out.println(sb);
    }

    private static void compress(int sr, int er, int sc, int ec) {
        if (isUniform(sr, er, sc, ec)) {
            sb.append(board[sr][sc]);
            return;
        }

        sb.append("(");
        int midR = (sr + er) / 2;
        int midC = (sc + ec) / 2;

        compress(sr, midR, sc, midC); // 1사분면
        compress(sr, midR, midC, ec); // 2사분면
        compress(midR, er, sc, midC); // 3사분면
        compress(midR, er, midC, ec); // 4사분면

        sb.append(")");
    }

    private static boolean isUniform(int sr, int er, int sc, int ec) {
        int value = board[sr][sc];
        for (int r = sr; r < er; r++) {
            for (int c = sc; c < ec; c++) {
                if (board[r][c] != value) {
                    return false;
                }
            }
        }
        return true;
    }
}

4. 코드 분석

시간 복잡도

• 재귀 호출에서 각 단계마다 4개의 부분으로 나누어 호출하므로, O(N^2) 복잡도를 가짐.
• 최악의 경우 2^6 x 2^6 = 64 x 64 = 4096번의 연산이 필요하지만, 압축이 잘 이루어진다면 더 적은 연산으로 해결 가능.

메모리 사용 최적화

• StringBuilder를 사용하여 문자열 연산을 최적화.
• BufferedReader를 사용하여 입력을 빠르게 처리.

주요 함수 설명

1. compress(int sr, int er, int sc, int ec)
   • 현재 영역이 모두 같은 값인지 검사 후, 그렇다면 숫자 출력.
   • 아니라면 4개의 영역으로 나누고 재귀적으로 처리.
2. isUniform(int sr, int er, int sc, int ec)
   • 주어진 영역이 모두 같은 값인지 검사.

5. 개선할 점 및 대체 방법

개선할 점

1. 압축 검사 최적화
   • 현재 isUniform 함수에서 2중 for문을 사용하여 모든 값을 검사하지만, 이 과정을 최적화할 방법을 고려 가능.
   • 예를 들어, 합계를 미리 계산해두면 비교 연산을 줄일 수 있음.
2. 메모리 사용 최적화
   • board 배열을 char[][]로 선언하면, 불필요한 int 변환을 줄일 수 있음.

대체 방법

• DFS(깊이 우선 탐색) 방식 적용 가능
  • 쿼드트리는 본질적으로 DFS와 유사한 구조를 가짐.
  • 반복문을 활용한 비재귀적 방식으로 구현할 수도 있음.