[BOJ]1992号:四叉木(Java)
問題Silver 1
1992号:四叉木
に答える
分割征服アルゴリズムの問題は,圧縮がなければ4つの領域に分割して演算する必要がある.
圧縮後に関数内で領域を分割する必要がないことを確認します(canZip)
圧縮可能な場合(=範囲内のすべての数値が等しい場合)は、StringBuilder変数に格納されます.
圧縮できない場合はsizeと現在の開始位置(ci,cj)で4つの領域に分割し、再帰を呼び出す
コード#コード#
import java.io.*;
import java.util.*;
public class Main{
static StringBuilder sb; //결과값 저장 변수
static int[][] arr;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
arr = new int[N][N];
for(int i = 0 ; i < N ; i++) {
String str = br.readLine();
for(int j = 0 ; j< N; j++) {
arr[i][j] = str.charAt(j)-'0'; //문자형->정수형 변환
}
}
sb = new StringBuilder();
quardTree(N, 0, 0);
System.out.println(sb.toString());
}
static boolean canZip(int size, int ci, int cj) {
int tmp = arr[ci][cj];
for(int i =0 ; i < size; i++) {
for(int j =0 ; j<size ; j++) {
if(tmp != arr[ci+i][cj+j])
return false;
}
}
return true;
}
static void quardTree(int size, int ci, int cj) {
if(canZip(size, ci, cj)) { //압축할 수 있는지 => 범위내 모든 숫자가 같은지 판별
sb.append(arr[ci][cj]); //같다면, sb에 바로 저장
return;
}
sb.append('('); //분할 시, ( 삽입 후 연산
quardTree(size/2, ci, cj); //왼쪽 위
quardTree(size/2, ci, cj+size/2); //오른쪽 위
quardTree(size/2, ci+size/2, cj); //왼쪽 아래
quardTree(size/2, ci+size/2, cj+size/2); //오른쪽 아래
sb.append(')');
}
}
Reference
この問題について([BOJ]1992号:四叉木(Java)), 我々は、より多くの情報をここで見つけました https://velog.io/@dot2__/BOJ-1992번-쿼드트리Javaテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol