알고리즘/백준
[Java] 백준 1992. 쿼드트리
24시간이모자란
2023. 6. 27. 01:02
문제
1992번: 쿼드트리
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또
www.acmicpc.net
풀이
풀이 알고리즘은 다음과 같다.
- 주어진 크기 N에서 2중for 탐색으로 배열을 모두 1 인지 0 인지 검사를 한다.
- 모두 1이거나 0 이면 1 또는 0 을 출력한다.
- 그렇지 않으면, 재귀 탐색으로 subarray를 탐색을 구현한다.
코드
import java.io.*;
import java.util.*;
public class Main {
int m[][];
int ans;
int theta;
BufferedWriter bw;
public static void main(String args[]) throws IOException {
Main m = new Main();
m.solution();
}
public void solution() throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
String str;
m = new int[N][N];
for(int i = 0; i< N ;i++){
str = br.readLine();
for(int j = 0 ;j < N ;j ++){
m[i][j] =str.charAt(j) -'0';
}
}
recursiveF(N, 0, 0);
bw.close();
}
public void recursiveF(int N , int x, int y)throws IOException{
int n = check(x,y,N);
if(n != -1 ){
bw.write(Integer.toString(n));
}else if( N/2 >0){
bw.write("(");
recursiveF(N/2, x, y);
recursiveF(N/2, x, y + N/2);
recursiveF(N/2, x + N/2, y);
recursiveF(N/2, x+N/2, y+N/2);
bw.write(")");
}
}
public int check(int x, int y, int N){
int z = 0;
boolean f = false;
for(int i = x; i< x + N ;i++){
if(f)break;
for (int j = y; j < y + N; j++) {
if(f)break;
if(m[i][j] != z){
f = true;
}
}
}
if(!f)return z;
f = false;
z = 1;
for(int i = x; i< x + N ;i++){
if(f)break;
for (int j = y; j < y + N; j++) {
if(f)break;
if(m[i][j] != z){
f = true;
}
}
}
if(!f)return z;
return -1;
}
}