[백준] 1992번 쿼드 트리 (java, 완전탐색)

www.acmicpc.net/problem/1992

1992번: 쿼드트리

맵을 1/4로 쪼개서 만드는 것은 한 번 해봐서 이번에는 익숙하게 했다. 안해봤다면 어려웠을 것이다. 

 

1/4로 쪼갠 행과 열의 시작점과 길이(현재길이len의 반)을 재귀로 돌면된다.

 시작점의 수와 해당 범위안에서 for문을 돌면서 하나라도 다른 원소가 있으면 다시 1/4로 쪼개서 재귀를 돌아준다.

 

재귀를 돌기 전에 (을 더하고 모든 원소가 갔을 때 시작점의 원소를 더해주고 재귀가 끝나면 )을 더해준다. 

 

import java.util.Scanner;

public class Main {
	static int n;
	static int map[][];
	static String ans="";
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		map=new int[n][n];
		for (int i = 0; i < n; i++) {
			String s=sc.next();
			for (int j = 0; j < n; j++) {
				map[i][j]=s.charAt(j)-'0';
			}
		}
        //압축을 시작해봅시다
		compress(0,0,n);
		System.out.println(ans);
	}
	
	private static void compress(int sy,int sx,int len) {
		//길이가 1이라면 더이상 못쪼갠다. 
		if(len==1) {
			ans+=Integer.toString(map[sy][sx]);
			return;
		}
		// 시작점의 원소 
		int cur=map[sy][sx];
		boolean passed=true; //해당 범위안에서 모든 원소가 같다면 패스
		for (int y = sy; y < sy+len; y++) { // 검사하는 범위 
			for (int x = sx; x < sx+len; x++) {
				if(map[y][x]!=cur) {//하나라도 다르면 false
					passed=false;
					break;
				}
			}
			if(passed==false)break; 
		}
		
		if(passed==false) { // 원소가 다르다면 쪼개줘야지
			ans+="(";
			for (int i = sy; i < sy+len; i+=len/2) { //쪼갠 사방진의 시작 주소를 넘겨준다
				for (int j = sx; j < sx+len; j+=len/2) { //길이도 반으로 쪼개준다
					compress(i,j,len/2);
					
				}
			}
			ans+=")";
		}else {
			
			ans+=Integer.toString(cur); //모든 원소가 같을 때는 값만 더해준다.
			
		}
		
		
		
		
		
	}

}