https://www.acmicpc.net/problem/1992
배열 전체를 바라봤을 때 모두 0이거나 1일 때 해당 값을 출력함
만약 배열 전체가 0또는 1로 이뤄져 있지 않을 때, 해당 배열을 4개로 쪼개서 다시 배열을 확인함, 단 쪼개지는 경우 괄호로 묶어서 표시함
package algo.bj.s1_1992;
import java.io.*;
import java.util.*;
public class Main {
static int[][] arr;
static StringBuilder sb;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
sb = new StringBuilder();
int N = Integer.parseInt(st.nextToken());
arr = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
String s = st.nextToken();
for (int j = 0; j < N; j++) {
arr[i][j] = s.charAt(j) - '0';
}
}
// 탐색 할 한 변의 넓이, 시작 x, 시작 y
recursive(N, 0, 0);
System.out.println(sb);
}
private static void recursive(int n, int startX, int startY) {
// basis part
if (n == 1) {
if (arr[startX][startY] == 0) {
sb.append(0);
}
if (arr[startX][startY] == 1) {
sb.append(1);
}
return;
}
int count = 0;
// inductive part
for (int i = startX; i < startX + n; i++) {
for (int j = startY; j < startY + n; j++) {
count += arr[i][j];
}
}
if (count == 0) {
sb.append(0);
} else if (count == n * n) {
sb.append(1);
} else {
sb.append("(");
recursive(n / 2, startX, startY);
recursive(n / 2, startX, startY + n / 2);
recursive(n / 2, startX + n / 2, startY);
recursive(n / 2, startX + n / 2, startY + n / 2);
sb.append(")");
}
}
}
- 예시1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
만약 예시 1과 같이 모든 값이 0으로 나온다면 출력 결과로 0 이 나오게 됩니다.
- 예시 2
1 1 0 0
1 1 1 1
0 0 1 1
0 0 1 1
하지만 예시2와 같이 배열이 존재한다면, 한번에 표현하지 못하므로 ()로 묶고,
나뉜 네가지 영역을 다시 확인해야 합니다.
이때 네 영역은 각각 1 0 0 1로 표현가능하므로 (1001) 이 나오게 됩니다.
이를 재귀를 통해서 반복하여 확인하도록 구현하였습니다.
~~
해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.
혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!
[SWEA] 7465 창용마을무리의개수 (D4 / 서로소) - Java (0) | 2023.03.07 |
---|---|
[SWEA] 3289 서로소집합 (D4 / 서로소) - Java (0) | 2023.03.07 |
[SWEA] 9229 한빈이 Spot Mart (D3, 조합) - Java (0) | 2023.02.25 |
[Baekjoon] 백준 10163 색종이 (B1, 구현) - Java (1) | 2023.02.21 |
[Baekjoon] 백준 3040 백설 공주와 일곱 난쟁이 (B2, 조합) - Java (0) | 2023.02.21 |