백준 1992번 쿼드트리 JAVA

링크텍스트

설명

풀이 흐름 설명

이 문제는 쿼드트리를 구현하는 전형적인 재귀 기반 분할정복 문제다.
주어진 영역이 모두 같은 값이면 그대로 출력하고 서로 다른 값이 섞여 있다면 4등분하여 각각을 다시 압축하는 구조였다.

먼저 입력으로 주어진 N×N 배열을 arr에 저장하였다.
이후 recursion(r, c, size) 형태의 재귀 함수를 정의하였다.

재귀 함수는 현재 영역의 시작 좌표 (r, c)와 한 변의 길이 size를 인자로 받도록 구현하였다.
가장 먼저 현재 영역의 기준값을 arr[r][c]로 설정하였다.
그 다음 이 영역이 모두 같은 값인지 확인하였다.
이중 반복문을 통해 size × size 범위를 순회하며 하나라도 다른 값이 존재하면 압축이 불가능하다고 판단하였다.

모든 값이 동일한 경우 → 해당 숫자를 문자열로 반환하였다.
서로 다른 값이 존재하는 경우 → 영역을 4등분하여 재귀 호출하였다.

4등분은 다음과 같이 진행하였다.
왼쪽 위: recursion(r, c, ns)
오른쪽 위: recursion(r, c + ns, ns)
왼쪽 아래: recursion(r + ns, c, ns)
오른쪽 아래: recursion(r + ns, c + ns, ns)

여기서 ns = size / 2로 설정하였다.
네 영역의 결과를 괄호로 묶어 반환하도록 구성하였다.
이 과정을 재귀적으로 반복하여 최종 압축 문자열을 완성하였다.

고민과 해결

처음에는 왼쪽 위가 (r, c)이고 오른쪽 위가 (r, c + ns)인지 직관적으로 와닿지 않았다.
2차원 배열에서
행(row)은 아래 방향으로 증가하고
열(column)은 오른쪽 방향으로 증가한다는 점을 다시 정리하였다.

따라서
오른쪽 영역은 열을 증가시켜야 하므로 c + ns
아래 영역은 행을 증가시켜야 하므로 r + ns
라는 점을 이해하였다.
이후 4분할 좌표 계산이 명확해졌다.

분할정복 구조에 대한 이해

이 문제는 현재 문제를 동일한 작은 문제 4개로 나누는 구조였다.
재귀 호출이 단순 반복이 아니라 문제를 점점 작게 쪼개는 과정이라는 점을 의식하면서 구현하였다. 쿼드트리는 대표적인 분할정복 예제라는 점을 다시 확인할 수 있었다.
시간복잡도: O(N²), 공간복잡도: O(N²)

회독

• [ x ] 1회
• 2회
• 3회

코드

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

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

        for(int i=0;i<n;i++){
            String s = br.readLine();
            for(int j=0;j<n;j++){
                arr[i][j] = s.charAt(j)-'0';
            }
        }

        System.out.println(recursion(0,0,n));
    }

    public static String recursion(int r, int c, int size){
        int now = arr[r][c];
        boolean same = true;

        for(int i=r;i<r+size;i++){
            for(int j=c;j<c+size;j++){
                if(arr[i][j]!=now){
                    same = false;
                    break;
                }
            }
            if(!same) break;
        }
        
        if(same){
            return Integer.toString(now);
        }else{
            int ns = size/2;
            
            StringBuilder sb = new StringBuilder();
            
            sb.append("(");
            sb.append(recursion(r, c, ns)); // 왼쪽 위
            sb.append(recursion(r, c+ns, ns)); // 오른쪽 위
            sb.append(recursion(r+ns, c, ns)); // 왼쪽 아래
            sb.append(recursion(r+ns, c+ns, ns)); // 오른쪽 아래
            sb.append(")");
            
            return sb.toString();
        }
    }
}