백준 온라인 저지 1992번 '쿼드트리'
Java 알고리즘 문제풀이
풀이
이 문제는 분할정복(Divide and Conquer)로 풀면된다.
분할정복 사실은 정말 쉬운 개념이다.
복잡한 문제를 해결할 수 있는 작은 단위로 나누어 처리하고 이것을 합치면 된다.
이 문제를 풀면 백준 1780번 문제 종이의 개수도 아주 쉽게 풀 수 있을 것이다.
(유사한 문제 풀기 -> 백준 1780번 문제종이 https://developer-mac.tistory.com/38)
그리고 쿼드트리는 단순히 노드가 4개 있는 것이라고 생각하면 된다.
즉, 4개로 쪼개서 4개의 노드가 생겨난다고 생각하면 된다.
먼저 입력을 받은 후 divide 함수에서 재귀적으로 동작하고 if 문을 두어 모든 원소가 0이거나 1일때 빠져나오게 하면되는 문제다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class beak_1992 {
private static int n, m;
private static int map[][];
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine().trim());
map = new int[n][n];
int[] num = new int[n];
for (int i = 0; i < n; i++) {
String num_1 = br.readLine();
for (int j = 0; j < n; j++) {
num[j] = num_1.charAt(j);
map[i][j] = (int)num[j] - 48;
}
}
divide(0, 0, n);
}
private static boolean check(int row, int col, int n) {
int std = map[row][col];
for (int i = row; i < row + n; i++) {
for (int j = col; j < col + n; j++) {
if (std != map[i][j]) {
return false;
}
}
}
m = std;
return true;
}
private static void divide(int row, int col, int n) {
if (check(row, col, n)) {
System.out.print(m);
} else {
System.out.print("(");
int s = n / 2;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
divide(row + s * i, col + s * j, s);
}
}
System.out.print(")");
}
}
}
DFS (깊이 우선 탐색) (0) | 2022.03.19 |
---|---|
BFS (너비 우선 검색) 정리 (0) | 2022.03.19 |
완전탐색 (Brute-Force) (0) | 2022.03.19 |
동적 계획법 (DP) 정리 (0) | 2022.03.19 |
[OS]프로세스(Process)와 스레드(Thread)의 차이/멀티 프로세스와 멀티 스레드의 개념 ,특징, 장단점 (0) | 2022.03.19 |