[백준] 1992번 쿼드트리(java)

문제 Silver 1

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

---

풀이

압축이 되지 않으면 4구역으로 나누어서 연산을 진행해야 하는 분할정복 알고리즘 문제

함수 내에서 구역을 나눌 필요 없이 압축이 되는지부터 확인(canZip)

압축이 가능하다면 (=범위내에 모든 수가 같다면) 해당 수를 StringBuilder변수에 저장

압축이 불가능하다면, size와 현재 시작위치(ci, cj)를 기준으로 4구역으로 나눈 후 재귀 호출

 

코드

import java.io.*;
import java.util.*;

public class Main{
	static StringBuilder sb;		//결과값 저장 변수
	static int[][] arr;				
	public static void main(String[] args) throws Exception{
		BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		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';			//문자형->정수형 변환
			}
		}
		sb = new StringBuilder();
		quardTree(N, 0, 0);
		System.out.println(sb.toString());
	}
	static boolean canZip(int size, int ci, int cj) {
		int tmp = arr[ci][cj];
		for(int i =0 ; i < size; i++) {
			for(int j =0 ; j<size ; j++) {
				if(tmp != arr[ci+i][cj+j])
					return false;
			}
		}
		return true;
	}
	static void quardTree(int size, int ci, int cj) {
		if(canZip(size, ci, cj)) {		//압축할 수 있는지 => 범위내 모든 숫자가 같은지 판별
			sb.append(arr[ci][cj]);		//같다면, sb에 바로 저장
			return;
		}
		sb.append('(');					//분할 시, ( 삽입 후 연산
		quardTree(size/2, ci, cj);		//왼쪽 위
		quardTree(size/2, ci, cj+size/2);	//오른쪽 위
		quardTree(size/2, ci+size/2, cj);	//왼쪽 아래
		quardTree(size/2, ci+size/2, cj+size/2);	//오른쪽 아래
		sb.append(')');		
	}
}