[JAVA 자바] 백준 1992번 : 쿼드트리

▶ 문제

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

1992번: 쿼드트리

 

▶ 설명

쿼드트리란?

자식 노드가 4개인 트리를 말한다. (참고로 자식 노드가 2개면 이진트리라고 한다.)

쿼드트리는 2차원에서 많이 사용하는데 4등분으로 재귀적으로 분할한다는 특징이 있다.

이러한 특징은 분할 정복 알고리즘과 매치된다. 

 

문제 설명

문제를 살펴보면 아래와 같이 흑백을 1과 0으로 표현한다고 되어 있다.

0과 1을 2차원 배열로 입력 받아 저장한 뒤, 모두 같은 숫자인지 아닌지를 체크한 후

같은 색(숫자)이면 0또는 1로 반환하고, 다르면 다시 4분할하여 모두 같은 숫자인지 아닌지를 체크하면 되겠다.

 

함수 호출 순서

4분할 한 뒤 어느 구역부터 탐색할지는 문제에서 주어졌다.

[본문 내용]

"주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다 "

위에서 언급한대로  함수 호출 순서를 지켜야 한다는 점에 유의하여야 한다.

 

 

▶ 문제 풀이

🌱 풀이

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	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];
		//입력으로 주어진 0과 1을 arr 배열 값으로 받기.
		for (int i = 0; i < arr.length; i++) {
			String str = br.readLine();
			for (int j = 0; j < str.length(); j++) {
				arr[i][j] = str.charAt(j) - '0';
			}
		}

		//arr 배열의 첫 인덱스[0,0]와 row/col 길이를 인수로 넘겨주기.
		quadTree(0, 0, n);
		System.out.println(sb);
	}

	private static void quadTree(int x, int y, int size) {
		// 색이 같으면 색을 출력
		if (sameColor(x, y, size)) {
			sb.append(arr[x][y]);
		}
		// 색이 다르면 다시 분할하여 검색
		else {
			int halfSize = size / 2;

			sb.append("(");
			quadTree(x, y, halfSize); //왼쪽 위
			quadTree(x, y + halfSize, halfSize);//오른쪽 위
			quadTree(x + halfSize, y, halfSize);//왼쪽 아래
			quadTree(x + halfSize, y + halfSize, halfSize);//오른쪽 아래
			sb.append(")");
		}
	}

	private static boolean sameColor(int x, int y, int size) {
		//요소 1개는 항상 같은 색을 가지기 때문에 true 반환
		if (size == 1) {
			return true;
		} else {
			//2개 이상의 요소를 탐색해야 할 경우 첫번째 값을 기준으로 나머지 요소들과 비교하기.
			int color = arr[x][y];

			for (int i = x; i < x + size; i++) {
				for (int j = y; j < y + size; j++) {
					//다른 색이 발견되면 false를 반환.
					if (arr[i][j] != color) {
						return false;
					}
				}
			}
			//비교가 모두 끝나고도 다른 색이 발견된 적 없으면 true를 반환.
			return true;
		}
		
	}

}

 

 

 

▶ Log

• 분할정복 카테고리 중에서 처음에 풀었던 색종이 문제의 변형이여서 새로운 아이디어가 추가되지는 않았다.

 

• 쿼드트리 설명 잘 되어있는 곳 :  https://st-lab.tistory.com/230