백준 - 1992 : 쿼드 트리 [자바]
구글링 참고해서 풀었습니다...
다시 폴어볼 것‼️
import java.util.*;
import java.io.*;
public class Main {
// 쿼드트리(Quad Tree) : 흑백 영상을 압축하여 표현하는 데이터 구조
// 0 : 흰 점, 1 : 검은 점
// 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축
// 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 0
// 주어진 영상이 모두 1로만 되어 있으면 압축 결과는 1
// 0, 1이 섞여 있으면, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 4개의 영상으로 나누어서 압축
static int[][] video;
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()); // 영상의 크기 N
// 2의 제곱 수, 1<= N <= 64
video = new int[N][N];
for (int i = 0; i < N; i++) {
String str = br.readLine();
for (int j = 0; j < N; j++) {
video[i][j] = str.charAt(j) - '0';
}
}
quadTree(0, 0, N);
System.out.println(sb);
br.close();
}
static void quadTree(int r, int c, int N) {
if (check(r, c, N)) { // 압축 가능하면 압축
sb.append(video[r][c]);
return;
}
// 압축 불가능하면 요렇게
int size = N / 2;
sb.append("(");
quadTree(r, c, size); // 왼쪽 위
quadTree(r, c + size, size); // 오른쪽 위
quadTree(r + size, c, size); // 왼쪽 아래
quadTree(r + size, c + size, size); // 오른쪽 아래
sb.append(")");
}
// 분할한 거 안에 다 같으면 true 리턴
// 다른 거 포함되어있으면 false 리턴
static boolean check(int r, int c, int N) {
int value = video[r][c];
for (int i = r; i < r + N; i++) {
for (int j = c; j < c + N; j++) {
if (video[i][j] != value) {
return false;
}
}
}
return true;
}
}
Author And Source
이 문제에 관하여(백준 - 1992 : 쿼드 트리 [자바]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@heoeunah/백준-1992-쿼드-트리-자바저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)