[백준 1992번] 쿼드트리- java

문제 설명

1. N이 주어진다.

2. NxN배열에 해당하는 숫자들이 주어지고, 1은검은색, 0은흰색이다.

3. 주어진 배열을 왼위/오위/왼아/오아 이렇게 4부분으로나누어 다1이면 1, 다0이면 0을 받는다.

4. 만약 전체가 1또는 0이 아닌 경우 또 4부분으로 나누어 풀이한다.

5. 저 크게 나누면 괄호로 표시해 준다. 그렇게 구한 답을 return하면 된다.

풀이 과정

 1. 분할 정복 문제이다.

 2. 값들을 더 작은 수로 나누고, 그곳에서부터 조합해 맞추어 나가면 된다.

 3. 전체 크기에 대해 모두 같은 영역으로 이루어졌는지 판단하고, 맞으면 그 숫자를 더해주며 아닌 경우 다시 분할해 주면 된다.

 4. 예를 들어 

모두 1인 경우                  - 그냥 답에 1 더하기

중간에 다른 답이 있는 경우 - 괄호를 펼쳐주고 다시 4개로 나누어 풀어주기 -> 끝나고 다시 괄호 닫기

 5. 기초적인 분할 정복 문제이기 때문에 이걸 통해 다른 분할정복을 풀 수 있도록 연습하는 게 좋을 것 같다. 좋은 문제인듯..

코드

import java.util.Scanner;

public class Main {
	public static int coor[][];
	public static int N;
	public static String ans = "";
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		coor = new int[N][N];
		
		for(int i=0; i<N; i++) {  // 크기 N, 그 좌표들을 각각 모두 입력받는다.
			String input = sc.next();
			for(int j=0; j<N; j++) coor[i][j] = input.charAt(j) - '0';
		}
		QT(0, 0, N);  // 분할정복 시작!
		System.out.println(ans);	// 분할 정복으로 얻은 값을 저장하면 된다.
	}
	public static void QT(int x, int y, int size) {
		int nowVal = coor[x][y]; // 분할정복 시작값을 입력받는다.
		if(compression(x, y, size, nowVal)) {	// 그걸 기점으로 해당 영역을 압축할 수 있는지 판단한다.
			ans += nowVal;	// 위에가 true라면 압축 가능한 값이니 그냥 압축해버린다.
			return;  // 뒤의 범위 시행 필요x
		}
		
        // 압축이 불가능한 경우 다시 4가지 범위에 분할정복 실시
		ans += "(";		// 분할정복을 시행하므로 괄호를 열어준다.
		QT(x, y, size/2);	// 왼쪽위
		QT(x, y+size/2, size/2);  // 오른쪽위
		QT(x+size/2, y, size/2);  // 왼쪽아래
		QT(x+size/2, y+size/2, size/2);  // 오른쪽아래
		ans += ")";  // 해당 분할정복이 끝나면 이를 닫아준다.
	}
	public static boolean compression(int x, int y, int size, int nowVal) { // 압축가능여부 판단함수
		for(int i=x; i<x+size; i++) {	// x축의 범위
			for(int j=y; j<y+size; j++) {  // y축의 범위
				if(nowVal!=coor[i][j]) {	// 만약 다른 값이 있으면 이건 압축할 수 없다.
					return false;  // ㅇㅇ
				}
			}
		}
		return true;	// 모두 같은 값이면 압축 가능하다.
	}
}