알고리즘
[Java] 백준 1992번 쿼드트리
J3SUNG
2023. 2. 21. 19:25
728x90
분할 정복 문제입니다.
사각형을 4개로 나누어서 조건에 부합하는지 확인합니다.
부합하지 않으면 부합할 때까지 나누어줍니다.
나누어진곳이 0으로 이루어졌다면 0을 출력하고 1로 이루어졌다면 1을 출력합니다.
나누어 질 때 ( )로 덮어 줍니다.
public static void Func(int y, int x, int size) {
int num = map[y][x];
for(int i=0; i<size; ++i) {
for(int j=0; j<size; ++j) {
if(map[y+i][x+j] != num) {
ans += "(";
Func(y, x, size/2);
Func(y, x+size/2, size/2);
Func(y+size/2, x, size/2);
Func(y+size/2, x+size/2, size/2);
ans += ")";
return;
}
}
}
ans += num == 0 ? "0" : "1";
}
전체 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
static int n;
static String ans = "";
static int[][] map;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(br.readLine());
map = new int[n][n];
for(int i=0; i<n; ++i) {
String s = br.readLine();
for(int j=0; j<n; ++j) {
map[i][j] = s.charAt(j) == '0' ? 0 : 1;
}
}
Func(0, 0, n);
bw.write(ans);
bw.close();
}
public static void Func(int y, int x, int size) {
int num = map[y][x];
for(int i=0; i<size; ++i) {
for(int j=0; j<size; ++j) {
if(map[y+i][x+j] != num) {
ans += "(";
Func(y, x, size/2);
Func(y, x+size/2, size/2);
Func(y+size/2, x, size/2);
Func(y+size/2, x+size/2, size/2);
ans += ")";
return;
}
}
}
ans += num == 0 ? "0" : "1";
}
}