백준
Q2_1992(쿼드트리)
mozzi329
2022. 9. 1. 21:29
728x90
📌 문제
문제)
쿼드트리 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다.
흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.
주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다.
만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다
위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면"(0(0011)(0(0111)01)1)"로 표현된다.
N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.
입력)
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다.
N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다.
두 번째 줄부터는 길이 N의 문자열이 N개 들어온다.
각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.
출력)
영상을 압축한 결과를 출력한다.
시간 제한 : 2초
메모리 제한 : 128 MB
📌 문제 분석❗️
❗️전체 영역을 계속 4등분으로 쪼개 조건을 확인한다.
❗️모든 영역이 0이면 0, 모든 영역이 1이면 1, 섞여있다면 ()로 묶는다.
- 탐색의 방향은 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순이다.
- 탐색 범위의 값이 전부 1이라면 1 문자열을 추가한다.
- 탐색 범위의 값이 전부 0이라면 0 문자열을 추가한다.
- 0과 1이 섞여있다면 괄호를 추가하고, 해당 탐색 범위를 다시 4등분하여 탐색한다. 탐색된 결과 문자열은 괄호 안에 입력된다.
- Q1_2630 색종이 문제와 거의 비슷하다.
📌 진행
❗️전역 변수 선언
private static char[][] quadTreeArr;
private static StringBuilder result = new StringBuilder();- quadTreeArr : 쿼드 트리 비교를 위한 2차원 배열
- result : 앞으로 계속 쌓아갈 문자열 스트링버퍼
❗️체크 메서드 생성
private static boolean checked(int row, int col, int N) {
char firstValue = quadTreeArr[row][col];
for (int i = row; i < row + N; i++) {
for (int j = col; j < col + N; j++) {
if(firstValue != quadTreeArr[i][j]) return false;
}
}
return true;
}값을 확인하기 위한 체크 메서드를 생성한다. 처음 값을 firstValue 변수에 담아준다.
해당 범위의 값이 모두 동일하다면 모든 값이 findValue와 동일할테니 통과한다면 true를, 다르다면 false를 리턴.
❗️재귀를 통한 분할 정복
private static void divideAndConquer(int row, int col, int N) {
if (checked(row, col, N)) {
result.append(quadTreeArr[row][col]);
return;
}
result.append('(');
divideAndConquer(row, col, N/2); // 왼 , 위
divideAndConquer(row, col + N/2, N/2); // 오 , 위
divideAndConquer(row+N/2, col, N/2); // 왼 , 아래
divideAndConquer(row+N/2, col+N/2, N/2); // 오 , 아래
result.append(')');
}- 범위 안의 값이 모두 동일하다면(checked 메서드를 만족) 결과 값에 해당 문자열을 append해준다.
그리고 리턴으로 재귀를 종료해준다. - 값이 다르다면 괄호 '()'로 묶고, 그 안을 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서로 재귀 함수를 호출해준다.
📌 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
private static char[][] quadTreeArr;
private static StringBuilder result = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
quadTreeArr = new char[N][N];
for (int i = 0; i < N; i++) {
quadTreeArr[i] = br.readLine().toCharArray();
}
divideAndConquer(0, 0, N);
System.out.println(result.toString());
}
private static boolean checked(int row, int col, int N) {
char firstValue = quadTreeArr[row][col];
for (int i = row; i < row + N; i++) {
for (int j = col; j < col + N; j++) {
if(firstValue != quadTreeArr[i][j]) return false;
}
}
return true;
}
private static void divideAndConquer(int row, int col, int N) {
if (checked(row, col, N)) {
result.append(quadTreeArr[row][col]);
return;
}
result.append('(');
divideAndConquer(row, col, N/2); // 왼 , 위
divideAndConquer(row, col + N/2, N/2); // 오 , 위
divideAndConquer(row+N/2, col, N/2); // 왼 , 아래
divideAndConquer(row+N/2, col+N/2, N/2); // 오 , 아래
result.append(')');
}
}