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

 
www.acmicpc.net/problem/1992

1992번: 쿼드트리

 

 

 

 

 

 

 

 

---

• 문제

 

 

 

 

 

 

이전 문제인 색종이 만들기 문제를 풀어보셨다면 매우 쉽게 풀 수 있는 문제다.

잘 모르겠는 경우 위 링크를 통해 한 번 풀어보고 오는 것을 추천한다.

 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

이진 트리(Binary Tree)는 자식 노드를 2개씩 갖는 트리였다면 쿼드 트리(Quad Tree)는 쉽게 말해서 자식 노드가 4개인 트리 자료구조를 의미한다. 

 

이전의 문제인 색종이 문제와 접근 방식 자체는 같은 구조로 보통 쿼드 트리의 경우 위 문제처럼 2차원 공간을 재귀적으로 4개의 영역으로 분할하여 데이터를 세분화 하는 방법으로 많이 사용된다.

 

말로는 이해하기 어려우니 간단하게 보면 다음과 같다.

 

2차원 공간 분할

 

이런식으로 각 레벨(깊이)에서 현재의 평면을 4개로 쪼개고 각 쪼개어진 4개의 영역에 대해 유사성을 검증하여 하나의 영역으로 묶는다거나 등 필요한 과정을 처리할 수도 있고, 또는 쪼개어진 영역을 또 4개의 영역으로 쪼개어 재귀호출을 더 할 수도 있는 것이다.

 

 

이를 응용하여 만약 3차원 공간을 분할하고 싶을 경우에는 8개의 영역으로 나누면 된다. 이는 옥트리(OcTree)라고도 한다.

 

3차원 공간 분할

 

 

 

이렇게 공간을 분할시켜 각 영역에 대해 처리하고자 하는 알고리즘을 적용시키는 방법이 쿼드 트리 적용 알고리즘이다.

 

 

 

자 그럼 문제를 이제 파악해보자.

 

앞서 지문에서 다음과 같은 그림이 나왔다. (좀 더 보기 편하게 수정했다.)

 

 

그리고 압축하기 위해서는 부분 영역이 모두 같은 색상이어야 한다.

즉, 하얀색(0)으로 이루어져 있거나, 검은색(1)로 이루러진 단일 색상 영역이어야 한다는 것이다.

 

위 그림에서는 일단 8×8 영역에서는 모두 같은 색상이 아니다.

 

그렇다면 뭐다? 쿼드트리 방식으로 공간을 4분할 하라는 것이다.

 

 

 

 

자 그럼 4×4 크기의 공간 4개를 얻을 수 있을 것이다.

 

문제에서는 왼쪽 위 → 오른쪽 위 → 왼쪽 아래 → 오른쪽 아래 순서대로 진행한다고 되어있으니 이에 맞춰 영역 번호를 매기겠다.

 

각 영역을 한 번 살펴보자. 영역 1은 모두 0으로 채워져있다. 즉, 단일 색상으로 이루어져 있다는 것이고, 이는 0으로 압축할 수 있다는 것이다. 쉽게 이미지화 하면 다음과 같이 변환된다는 것이다.

 

영역 1의 압축된 형태

 

 

 

 

 

그리고 영역 2의 경우 단일 색상으로 이루어져 있지 않다. 그럼 다시 영역 2의 공간을 4개의 부분공간으로 분할 하는 것이다. 그렇게 4개의 영역으로 나누면 다음과 같이 부분공간을 얻을 수 있다.

 

 

 

 

그럼 위 이미지에서 영역 2의 부분공간 2×2 크기의 공간 4개를 얻을 수 있다.

그럼 이 나눠진 부분 공간을 살펴보자.

2-1, 2-2 영역은 0(하얀색)으로 채워져 있으니 각각 0으로 압축 할 수 있다. 그리고 영역 2-3, 2-4 는 1(검은색)으로 각각 압축 할 수 있다. 즉, 다음과 같이 볼 수 있다는 것이다.

 

영역 2의 부분공간에 대한 압축

 

 

 

 

그 다음으로 영역 3에 대해 보자.

영역 3의 경우도 모두 같은 색이 아니라 영역 2와 마찬가지로 공간을 4개로 쪼개어야한다. 그러면 2×2 크기의 공간 4개를 얻을 수 있는데, 그 중 두 번째 공간인 영역 3-2 부분은 마찬가지로 같은 색이 아니므로 그 영역도 4개로 쪼개어야 한다. 즉, 다음과 같이 볼 수 있다.

 

 

 

그렇게 각 부분 공간에 대해 압축을 하면 다음과 같을 것이다.

 

 

 

 

그리고 마지막으로 영역 4는 모두 1(검정색)이므로 1로 압축하면 최종적으로 다음과 같은 그림을 얻을 수 있다.

 

 

 

 

 

 

위 과정을 하나로 묶어 전체적인 과정을 보자면 다음과 같다.

 

 

 

 

 

 

위와 같은 과정을 알고리즘으로 구성하면 된다.

 

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

이전 포스팅과 여타 다를 바 없이 아래와 같이 2가지 입력 방법을 통해 성능을 비교해보려 한다.

출력의 경우 하나로 묶어 출력할 수 있도록 모두 StringBuilder을  쓰도록 하곘다.

 

 

1. Scanner 

2. BufferedReader

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner]

 

import java.util.Scanner;

public class Main {
	
	public static int[][] img;		// 흑백 이미지
	public static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) {
    
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		img = new int[N][N];	
        
		for(int i = 0; i < N; i++) {
			String str = in.next();
			
			for(int j = 0; j < N; j++) {
				img[i][j] = str.charAt(j) - '0';
			}
		}
		
		QuadTree(0, 0, N);
		System.out.println(sb);
	}
	
	public static void QuadTree(int x, int y, int size) {
		
		// 압축이 가능할 경우 하나의 색상으로 압축해준다.
		if(isPossible(x, y, size)) {
			sb.append(img[x][y]);
			return;
		}
		
		int newSize = size / 2;	// 압축이 불가능 할 경우 사이즈를 절반으로 나누어야 한다.
		
		sb.append('(');	// 각 레벨(depth)에서 여는괄호로 시작해야한다. 
		
		QuadTree(x, y, newSize);						// 왼쪽 위
		QuadTree(x, y + newSize, newSize);				// 오른쪽 위
		QuadTree(x + newSize, y, newSize);				// 왼쪽 아래
		QuadTree(x + newSize, y + newSize, newSize);	// 오른쪽 아래
		
		sb.append(')');	// 해당 레벨이 끝나면 닫는괄호도 닫아준다.
			
		
	}
	
	
	// 압축이 가능한지 해당 공간을 체크해주는 함수
	public static boolean isPossible(int x, int y, int size) {
		int value = img[x][y];
		
		for(int i = x; i < x + size; i++) {
			for(int j = y; j < y + size; j++) {
				if(value != img[i][j]) {
					return false;
				}
			}
		}
		return true;
	}

}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

각 영역에서 가장 왼쪽 위를 기준점(포인터)삼아 x + size, y + size가 현재 공간의 크기라고 보면 된다.

 

 

 

 

---

- 방법 2 : [BufferedReader]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 

알고리즘 자체의 큰 차이는 없다.

 

 

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

public class Main {
	
	public static int[][] img;
	public static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		img = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			String str = br.readLine();
			
			for(int j = 0; j < N; j++) {
				img[i][j] = str.charAt(j) - '0';
			}
		}
		
		QuadTree(0, 0, N);
		System.out.println(sb);
	}
	
	public static void QuadTree(int x, int y, int size) {
		
		// 압축이 가능할 경우 하나의 색상으로 압축해준다.
		if(isPossible(x, y, size)) {
			sb.append(img[x][y]);
			return;
		}
		
		int newSize = size / 2;	// 압축이 불가능 할 경우 사이즈를 절반으로 나누어야 한다.
		
		sb.append('(');	// 각 레벨(depth)에서 여는괄호로 시작해야한다. 
		
		QuadTree(x, y, newSize);						// 왼쪽 위
		QuadTree(x, y + newSize, newSize);				// 오른쪽 위
		QuadTree(x + newSize, y, newSize);				// 왼쪽 아래
		QuadTree(x + newSize, y + newSize, newSize);	// 오른쪽 아래
		
		sb.append(')');	// 해당 레벨이 끝나면 닫는괄호도 닫아준다.
			
		
	}
	
	
	// 압축이 가능한지 해당 공간을 체크해주는 함수
	public static boolean isPossible(int x, int y, int size) {
		int value = img[x][y];
		
		for(int i = x; i < x + size; i++) {
			for(int j = y; j < y + size; j++) {
				if(value != img[i][j]) {
					return false;
				}
			}
		}
		return true;
	}

}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 27601197  -  방법 2 : BufferedReader

채점 번호 : 27601184  -  방법 1 : Scanner

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

 

---

• 정리

 

이 번 문제같은 경우 이전의 색종이 만들기 문제를 풀어보셨다면 그리 어려운 점은 없었을 것이다. 거의 유사한 과정이라 볼 수 있는데, 아무래도 탐색이 되는 과정을 이해할 수 있는가를 묻는 의도로 유사한 두 문제를 올린 게 아닐까 하는 생각이 든다.

 

만약 위의 과정을 완벽하게 이해할 수 있다면 여러분들이 직접 3차원 공간으로 확장하여 시도해보는 것도 좋을 것 같다.

 

혹여 설명이 어렵거나 이해가 안가신다면 댓글 남겨주시길 바란다. 최대한 빠르게 답변드리겠다.