1992번: 쿼드트리

문제

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)가 있습니다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 됩니다. 만약 0과 1이 섞여 있으면, 영상을 4개의 영역으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 괄호 안에 묶어서 표현합니다. N × N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 문제입니다.

• 입력: 첫째 줄에 영상의 크기 N (N은 1, 2, 4, 8, 16, 32, 64 중 하나)이 주어집니다. 둘째 줄부터 N개의 줄에 걸쳐 길이가 N인 0과 1로 이루어진 문자열이 주어집니다.
• 출력: 영상을 압축한 결과를 출력합니다.

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

풀이

영역을 4등분으로 나누며 재귀적으로 탐색하는 전형적인 분할 정복(Divide and Conquer) 문제입니다.

1. 영역 일치 확인: 현재 탐색 중인 영역(크기 n, 시작 좌표 y, x) 내의 모든 픽셀 값이 첫 번째 픽셀 값(tmp)과 일치하는지 이중 반복문을 통해 검사합니다.
2. 모두 일치하는 경우 (기저 조건): 영역 내의 모든 픽셀이 같다면 더 이상 분할할 필요가 없으므로 해당 픽셀 값(tmp)을 문자열로 반환합니다.
3. 불일치하는 경우 (분할 및 재귀 호출): 영역 내에 0과 1이 섞여 있다면, 압축이 불가능하므로 괄호 (를 열고 영역을 4등분(크기 n / 2)하여 각각 문제에서 요구하는 순서대로 재귀 호출합니다.
   • 왼쪽 위: go(y, x, n / 2)
   • 오른쪽 위: go(y, x + n / 2, n / 2)
   • 왼쪽 아래: go(y + n / 2, x, n / 2)
   • 오른쪽 아래: go(y + n / 2, x + n / 2, n / 2)
   • 재귀 호출이 끝난 후에는 괄호 )를 닫아 묶어준 문자열을 반환합니다.

코드

import java.io.*;

public class Main {
    static char[][] a;

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int n = Integer.parseInt(br.readLine());
       a = new char[n][n];
       
       // 입력 최적화: 한 줄을 통째로 읽어 문자 배열로 변환하므로 단일 반복문 사용
       for (int i = 0; i < n; i++) {
          a[i] = br.readLine().toCharArray();
       }

       bw.write(go(0, 0, n));

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

    static String go(int y, int x, int n) {
       char tmp = a[y][x];
       for (int i = y; i < y + n; i++) {
          for (int j = x; j < x + n; j++) {
             // 영역 내에 하나라도 다른 값이 있다면 4등분하여 분할 정복
             if (tmp != a[i][j]) {
                String ret = "(";
                ret += go(y, x, n / 2);             // 왼쪽 위
                ret += go(y, x + n / 2, n / 2);     // 오른쪽 위
                ret += go(y + n / 2, x, n / 2);     // 왼쪽 아래
                ret += go(y + n / 2, x + n / 2, n / 2); // 오른쪽 아래
                ret += ")";
                return ret;
             }
          }
       }

       // 영역 내의 모든 값이 같다면 해당 값 반환
       return String.valueOf(tmp);
    }
}

알고리즘 분류

분할 정복 (Divide and Conquer), 재귀 (Recursion)