[BOJ/Java] 1992. 쿼드트리

[BOJ/Java] 1992. 쿼드트리

1992번: 쿼드트리

---

문제 해석

이 문제는 2차원 배열에 저장된 흑백 이미지를 쿼드트리 방식으로 압축하는 문제다. 쿼드트리는 2차원 공간을 4분할하여, 각 구역이 모두 같은 값으로 이루어져 있다면 해당 값을 사용하고, 그렇지 않다면 더 작은 구역으로 나누어 재귀적으로 분석하는 압축 방식이다. 각 구역이 전부 0 또는 1인 경우에는 해당 숫자를 출력하고, 섞여 있는 경우에는 괄호로 묶어 각 사분면의 결과를 표시한다.

풀이 과정

제출된 코드는 주어진 2차원 배열에 대해 재귀적으로 쿼드트리 압축을 수행한다. 기본적인 로직은 다음과 같다.

 

1. recursive 함수는 현재 고려 중인 구역의 크기 n과 해당 구역의 좌측 상단 좌표 (x, y), 우측 하단 좌표 (X, Y)를 인자로 받는다.
2. 만약 n이 1이면, 현재 고려 중인 구역의 값(graph[x][y])을 StringBuilder에 추가한다.
3. 그렇지 않으면, 해당 구역의 모든 값을 합산하여 그 합이 n*n (전체가 1인 경우) 또는 0 (전체가 0인 경우)인지 확인한다.
4. 전체가 1이거나 0인 경우 해당 값을 추가하고, 그렇지 않은 경우 현재 구역을 4등분하여 각각에 대해 재귀 호출을 수행한다.

코드

package edu.ssafy.im.BOJ.Silver.S1.No1992;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		new Main().sol();
	}

	private int[][] graph; // 흑백 이미지 데이터를 저장할 2차원 배열
	private StringBuilder sb = new StringBuilder(); // 출력 결과를 저장할 StringBuilder

	private void sol() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine()); // 이미지의 크기 (N x N)
		graph = new int[n][n]; // 이미지 데이터를 저장할 배열 초기화

		for (int i = 0; i < graph.length; i++) {
			String string = br.readLine(); // 한 줄씩 입력 받음
			for (int j = 0; j < graph.length; j++) {
				graph[i][j] = string.charAt(j) - '0'; // 문자를 숫자로 변환하여 저장
			}
		}

		recursive(n, 0, 0, n, n); // 쿼드트리 압축 시작
		bw.write(sb.toString()); // 결과 출력
		bw.flush();
		bw.close();
	}

	private void recursive(int n, int x, int y, int X, int Y) {
		if (n == 1) {
			sb.append(graph[x][y]); // 단일 요소는 바로 결과에 추가
			return;
		}

		int sum = 0; // 현재 구역의 합을 계산
		for (int i = x; i < X; i++) {
			for (int j = y; j < Y; j++) {
				sum += graph[i][j];
			}
		}

		if (sum == n * n) {
			sb.append(1); // 전체가 1로만 구성된 경우
		} else if (sum == 0) {
			sb.append(0); // 전체가 0으로만 구성된 경우
		} else {
			int m = n/2; // 현재 구역을 4분할
			sb.append("(");
			recursive(m, x, y, x + m, y + m); // 좌상
			recursive(m, x, y + m, x + m, y + n); // 우상
			recursive(m, x + m, y, x + n, y + m); // 좌하
			recursive(m, x + m, y + m, x + n, y + n); // 우하
			sb.append(")");
		}
	}
}

시간 복잡도 분석

쿼드트리 알고리즘의 시간 복잡도는 최악의 경우 O(n2logn) 이다. 이는 각 재귀 호출마다 배열을 절반씩 분할하며 모든 요소를 확인하기 때문이다.

느낀점

쿼드트리 알고리즘을 구현하며, 재귀적 접근과 분할 정복의 개념을 실제 문제에 적용하는 방법을 체험할 수 있었다. 특히, 각 분할된 구역을 처리하는 로직의 효율성이 중요함을 깨달았으며, 이를 통해 알고리즘의 성능을 개선하는 경험을 얻었다.