[문제 설명]
분할정복 개념이 도입된다. 분할정복이란 큰문제를 작은 문제들로 분할해 가며 해결해 나아가는 것이다.(피보나치 수열도 이에 해당된다)
보통 재귀함수로 구현한다.
[문제 이해하기]
처음 배열이 구성되어있다고 생각하자
초록색 선처럼 했을때 전체 영역이 압축이 될것인가?
압축이 되면 바로 리턴
압축이 안되는 경우 4가지 영역으로 분할해야한다.
1,2,3,4 영역으로 나뉘어
초록색 선처럼 각 영역이 압축되는지 확인한다.
압축이 되면 바로 리턴
압축이 안되는 경우 또다시 4가지 영역으로 분할해야한다.
영역별로 왼쪽위->오른쪽 위 -> 왼쪽아래-> 오른쪽아래 순으로 압축이 되는 지 확인한다.
1,2,3,4 영역으로 나뉘어
초록색 선처럼 각 영역이 압축되는지 확인한다.
압축이 되면 바로 리턴
압축이 안되는 경우 또다시 4가지 영역으로 분할하여 결국 끝에는 1개의 영역까지 가게 될것이다.
1가지 부분은 자기자신이므로 자기 자신으로 압축이 될것이며
재귀 함수 리턴
진행방식은 단계를 N의 크기를 2로 나눈값으로 진행한다.
문제 예시에서는 8x8 영역이고 -> (4x4) -> (2x2)->(1x1) 이런순으로 확인 하였다.
그리고 문제에서는 압축이 된 영역에 대해 "(" , ")" 로 묶는 작업을 진행하였다.
그림이 미숙하지만 색깔별로 구분하였다.
그림처럼 4x4공간을 표현한것이다.
먼저 검은색 괄호는 8x8의 시작부분이며,
파란색 괄호 부분이 4x4의 시작부분이다.
그리고 파란색 괄호안 4가지 영역1,2,3영역은 압축이 되어 (101을 만들어내고
4번째 영역은 압축이 되지않아 빨간색괄호부분으로 시작해 0101영역으로 압축하고 빨간색 괄호 끝,파란색 괄호 끝 이렇게 감싸안아진행한다.
[전체 소스 코드]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class 쿼드트리 {
public static int arr[][];
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); // N은 2의 제곱수로 주어진다. 4 16 64.. 1 ≤ N ≤ 64의 범위를 가진다
arr = new int[N][N];
for(int i = 0; i <N; i++) {
String str = br.readLine();
for(int j = 0; j< N; j++) {
arr[i][j] = str.charAt(j)-'0';
}
}
// 구현
// 분할 정복은 재귀함수로 구현
solve(0,0,N);
}
private static void solve(int row, int col, int N) {
// 현재 위치부터 끝까지 압축이 가능한가
if(isPossible(row,col,N)) {
System.out.print(arr[row][col]);
return; // 가능하면 끝
}
N = N/2;
// 압축이 실패하면 압축을 위한 ( 괄호 시작
System.out.print("(");
// 4개의 영역으로 분리
//왼쪽 위
solve(row,col,N);
//오른쪽 위
solve(row,col+N,N);
// 왼쪽 아래
solve(row + N,col,N);
// 오른쪽 아래
solve(row+N,col+N,N);
// 압축 끝 (
System.out.print(")");
}
private static boolean isPossible(int row, int col,int N) {
// 각각의 좌표로 부터 N거리까지만큼 떨어진것을 측정하기 위해 각자 위치 row,col을 매개변수로 받고 N 까지 거리를 각 측정한다.
int current = arr[row][col];
for(int i = row; i < row +N; i++) {
for(int j = col; j < col +N; j++) {
if(current != arr[i][j]) {
return false; // 압축 실패
}
}
}
return true; // 압축 성공
}
}