👀 문제
https://www.acmicpc.net/problem/1992
👊 도전
1. 설계
- 분할정복 문제이다.
- 정사각형 범위를 줄여나가며 범위안에 같은 숫자들로 구성되어 있는지 확인한다.
2. 구현 (성공 코드)
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.util.*;
import java.io.*;
/**
* @author HEESOO
*
*/
class Main {
static int[][] map;
static String answer; // 출력할 문자열 저장하는 변수
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(br.readLine());
map=new int[n][n];
answer="";
// 맵 생성
for(int i=0;i<n;i++) {
String[] input=br.readLine().split("");
for(int j=0;j<n;j++) {
if(input[j].equals("1")) map[i][j]=1;
}
}
// 큰 정사각형부터 점점 범위를 좁혀나가며 체크
divide(0,0,n);
System.out.println(answer);
}
// map[row][col]을 시작으로 사이즈 n 정사각형 범위안에 같은 수로만 구성되어 있는지 체크
public static boolean isAble(int row, int col, int n) {
int value=map[row][col];
for(int i=row;i<row+n;i++) {
for(int j=col;j<col+n;j++) {
if(map[i][j]!=value) return false;
}
}
return true;
}
public static void divide(int row, int col, int n) {
if(isAble(row, col, n)) { // 같은 수로만 구성되어 있으므로
answer+=map[row][col];
}
else { // 아닐 경우 범위를 좁힘
answer+="(";
int newSize=n/2;
// 범위를 좁히고, 시작점을 지정하여 재귀호출
divide(row, col, newSize);
divide(row, col+newSize, newSize);
divide(row+newSize, col, newSize);
divide(row+newSize, col+newSize, newSize);
answer+=")";
}
}
}
3. 결과
🤟 성공 🤟
4. 설명
- 맵을 생성한다
- input이 한 줄 단위로 들어오기 때문에 split(““)으로 쪼갠 후, 1인 곳에 값을 넣는다.
- divide()로 정사각형 범위를 만들고, isAble()로 압축 가능한지 체크한다
- 파라미터 row, col은 map에서 시작점이고, n은 확인하고자 하는 정사각형 사이즈이다.
- isAble(row, col, n)을 통해 map[row][col]에서 오른쪽으로 n개, 아래로 n개만큼의 정사각형을 체크한다.
- value에 시작점 값을 넣는다. 압축이 가능하다면 해당 범위는 value로만 이루어져 있어야 한다. value와 다른 값이 나오면 false를 리턴한다.
- true를 리턴받았다면 압축 가능하므로 answer에 해당 값(map[row][col])을 저장한다.
- 아닐 경우, 정사각형 범위를 줄인다. 범위는 정사각형이므로 반으로 나눠야한다.
- 현재 위치(map[row][col])에서 newSize만큼 범위를 체크(1), 그 오른쪽 범위를 체크(2), 현재 위치 아래를 체크(3), 그 오른쪽을 체크(4)한다. 재귀를 이용한다. 순서가 바뀌면 안된다.
👏 해결 완료!
참고
- [백준] 1992번 자바 쿼드트리 https://log-laboratory.tistory.com/74