1992번: 쿼드트리
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또
www.acmicpc.net
한 구간에 0과 1로만 이루어져있으면 그 숫자를 출력, 아니면 괄호를 만들고 구간을 1/4로 나눠서 재귀를 돌려야하는 문제입니다.
우선 맨 처음 x, y에 들어있는 값을 저장해놓고, 이 값과 구간에 있는 모든 값과 비교해서
모두 같으면 ch 출력
다른게 있으면 인덱스를 이용하여 1/4로 나누었습니다.
여기서 재귀를 4번 돌리기 전에 "("를 출력해주고, 4번의 재귀가 끝나면 ")"를 출력해야합니다.
만약 size가 1이면 확인할 필요가 없기때문에 list[x][y]를 바로 출력하고 리턴합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static char list[][];
static int N;
static void func(int size, int x, int y) {
if (size == 1) {
sb.append(list[x][y]);
return;
}
boolean chk = false;
char ch = list[x][y];
for (int i = x; i < x + size; i++) {
for (int j = y; j < y + size; j++) {
if (ch != list[i][j]) {
chk = true;
break;
}
}
if (chk)
break;
}
if (chk) {
sb.append("(");
func(size / 2, x, y);
func(size / 2, x, (y + y + size) / 2);
func(size / 2, (x + x + size) / 2, y);
func(size / 2, (x + x + size) / 2, (y + y + size) / 2);
sb.append(")");
} else {
sb.append(ch);
}
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
list = new char[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
list[i] = st.nextToken().toCharArray();
}
}
public static void main(String[] args) throws Exception {
input();
func(N, 0, 0);
System.out.println(sb.toString());
}
}
|
cs |
'algorithm > Divide-and-Conquer' 카테고리의 다른 글
| boj 1074 Z (0) | 2021.02.16 |
|---|