[알고리즘-자바] 백준 1992번 쿼드트리

문제

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

1992번: 쿼드트리

언어

자바 Java

로직

이 문제는 구간 내의 모든 숫자가 동일한지 확인하여 구간 압축 결과를 출력하는 문제이다.

주의해야 할 점은 구간을 나누지 않았다면 숫자만 출력해야 하고, 구간을 나누고 압축을 했다면 () 괄호 안에 숫자를 출력해야 한다.

 

배열 저장

일단 크기가 n인 배열에 값을 저장합니다. getNumericValue의 경우 아스키코드로 표현된 숫자를 그대로 저장합니다.

ex) 아스키코드 '1'을 저장할 때 49를 저장하는 게 아니라 정수 1 그 자체로 저장합니다.

for (int i = 0; i < n; i++) {
    char[] cArr = br.readLine().toCharArray();
    for (int j = 0; j < n; j++)
        arr[i][j] = Character.getNumericValue(cArr[j]);
}

전체 배열 탐색

먼저 배열 전체를 탐색해야 합니다. (0,0)에 위치한 숫자부터 시작하여 배열의 끝까지 탐색을 하여 같은 숫자로만 이루어져 있는지 확인합니다. 

for (int i = y; i < y + length; i++) {
    for (int j = x; j < x + length; j++) {
        if (arr[i][j] != arr[y][x]) {
        // ..생략
        }
    }
}

구간 배열 탐색

조건문은 구간의 첫 번째 시작점으로부터 구간 내의 모든 숫자를 탐색하여 다른 숫자를 가진 경우에 실행됩니다. 예를 들어 전체 배열 탐색에서 (0,0) 위치의 값과 증가하는 (i, j) 위치의 값을 비교하여 다를 경우 조건문이 실행됩니다. 

정사각형 배열이기 때문에 배열을 절반으로 나누어 4등분을 할 수 있습니다. (가로, 세로 각각 2등분 -> 4등분)

if (arr[i][j] != arr[y][x]) {
    sb.append("(");
    length /= 2;
    traverse(arr, x, y, length);
    traverse(arr, x + length, y, length);
    traverse(arr, x, y + length, length);
    traverse(arr, x + length, y + length, length);
    sb.append(")");
    return;
}

 

재귀

구간 내의 숫자가 모두 동일해질 때까지 구간을 계속 나누어야 합니다. 이때 위에서 사용한 구간 탐색 배열의 코드를 재귀적으로 호출하면 됩니다. length는 위에서 말했듯이 해당 구간을 또다시 4등분으로 나누기 위하여 2로 나누어줍니다.

for (int i = y; i < y + length; i++) {
    for (int j = x; j < x + length; j++) {
        if (arr[i][j] != arr[y][x]) {
            sb.append("(");
            length /= 2;
            traverse(arr, x, y, length);
            traverse(arr, x + length, y, length);
            traverse(arr, x, y + length, length);
            traverse(arr, x + length, y + length, length);
            sb.append(")");
            return;
        }
    }
}

최종

재귀 함수를 통해 아래 사진과 같이 구간이 최종적으로 나뉘었습니다. 별도의 설명을 하지 안 해도 이해할 수 있을 거라 생각합니다.

최종적인 구간 개수

---

코드

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

public class Main {
    private static StringBuffer sb = new StringBuffer();
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            char[] cArr = br.readLine().toCharArray();
            for (int j = 0; j < n; j++)
                arr[i][j] = Character.getNumericValue(cArr[j]);
        }

        traverse(arr, 0, 0, n);
        System.out.println(sb);
    }

    private static void traverse(int[][] arr, int x, int y, int length) {
        for (int i = y; i < y + length; i++) {
            for (int j = x; j < x + length; j++) {
                if (arr[i][j] != arr[y][x]) {
                    sb.append("(");
                    length /= 2;
                    traverse(arr, x, y, length);
                    traverse(arr, x + length, y, length);
                    traverse(arr, x, y + length, length);
                    traverse(arr, x + length, y + length, length);
                    sb.append(")");
                    return;
                }
            }
        }
        if (arr[y][x] == 1)
            sb.append("1");
        else
            sb.append("0");
    }
}