[BOJ/백준] 1992번 : 쿼드트리 (Java)

📘 백준 1992번 : 쿼드트리

---

문제 바로가기

💡 문제 풀이

---

영상 데이터를 재귀적으로 4등분(분할 정복)하며 압축.

모든 픽셀이 같은 값인지 확인(재귀 종료 조건)하고, 같다면 해당 값 출력.

다르다면 괄호 ()로 감싸서 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 결과 연결.

왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래를 재귀적으로 함수를 호출하여 결과 도출.

✅ 코드 (Java)

---

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

// https://www.acmicpc.net/problem/1992
// 영상의 구조를 재귀적으로 4등분으로 나누어 압축
// 모든 픽셀이 같은 값인지 확인하고, 같다면 해당 값 출력
// 다르다면 괄호 ()로 감싸서 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 결과 연결
public class B1992_쿼드트리 {
	public static char[][] video; // 영상 구조

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine()); // 처음 영상 크기
		video = new char[N][N]; // 영상 구조
		for (int i = 0; i < N; i++) { // video[][] 채우기
			video[i] = br.readLine().toCharArray();
		}
		System.out.println(dc(0, 0, N)); // 압축 결과 출력
		br.close();
	}

	public static String dc(int x, int y, int size) { // 쿼드 트리 구조로 압축
		if (isSameColor(x, y, size)) { // 주어진 구역이 모두 같은 숫자면(재귀 종료 조건)
			return String.valueOf(video[x][y]); // 숫자 반환
		}
		int newSize = size / 2; // 분할 정복용 크기
		String leftTop = dc(x, y, newSize); // 왼쪽 위
		String rightTop = dc(x, y + newSize, newSize); // 오른쪽 위
		String leftBottom = dc(x + newSize, y, newSize); // 왼쪽 아래
		String rightBottom = dc(x + newSize, y + newSize, newSize); // 오른쪽 아래

		return "(" + leftTop + rightTop + leftBottom + rightBottom + ")"; // 분할한 값 합치기
	}

	public static boolean isSameColor(int x, int y, int size) { // 주어진 구역이 같은 색(숫자)인지 확인
		char first = video[x][y]; // 처음 값
		int xEnd = x + size;
		int yEnd = y + size;
		for (int i = x; i < xEnd; i++) {
			for (int j = y; j < yEnd; j++) {
				if (video[i][j] != first) { // 값이 다르면
					return false;
				}
			}
		}
		return true; // 값이 모두 같으면
	}
}

💾 제출 결과

---

보러 가기

🧩 새롭게 알게 된 점

---

• 쿼드 트리(Quad Tree) 구조

  • 2차원 공간을 반복적으로 네 부분으로 분할하는 트리 형태의 자료구조

  • 영상 압축에서 각 구역의 값이 같으면 해당 값을 저장하고, 그렇지 않으면 4개의 하위 구역으로 나누어 다시 같은 방식으로 처리

  • 일반적으로 이미지, 영상, 지리 정보처럼 2차원 데이터를 효율적으로 표현할 때 사용됨