[백준 2주차 - 1992] 쿼드트리 (Java)

📌 문제

 

 

📝문제 풀이

 

1) 전체가 0과 1 중 하나의 값으로만 이루어져 있는 지 확인

2) 하나의 값으로 일치 하지 않는다면 4등분하기 (왼쪽 위 / 오른쪽 위 / 왼쪽 아래 / 오른쪽 아래)

3) 모두 0이거나 모두 1일 때 값으로 표현하기

 

위 과정을 계속 반복하기 때문에 재귀함수를 활용하여 표현할 수 있다 여기서는 파라미터로 전체 사이즈, 시작 좌표 (y,x)를 넘겨야 한다

 

사이즈의 영역이 계속해서 4등분이 되기 때문에 분할정복 알고리즘을 사용하는 문제이다

 

재귀함수
함수에서 자신의 로직을 다시 호출해 작업을 수행하는 방식

 

분할정복(Divide and Conquer)
문제를 나눌 수 없을 때 까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘

 

 

💻코드

import java.util.*;
import java.io.*;
public class Main{
	static int map[][];
	static int n;
	static String str;

	static String quadTree(int y,int x,int size){
		//size가 1일때 
		if(size==1){ 
			return Integer.toString(map[y][x]);
		}
		int num=map[y][x]; //첫번 째 시작점
		str="";
		//0과 1로 일치 하지 않을 때
		for(int i=y;i<y+size;i++){
			for(int j=x;j<x+size;j++){
				if(num!=map[i][j]){
					str+="(";
					str+=quadTree(y,x,size/2);
					str+=quadTree(y,x+size/2,size/2);
					str+=quadTree(y+size/2,x,size/2);
					str+=quadTree(y+size/2,x+size/2,size/2);
					str+=")";
					return str;
				}
			}
		}
		//모두 0 또는 모두 1일때
		return Integer.toString(map[y][x]);
	}
	public static void main(String[]args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		n=Integer.parseInt(br.readLine());
		map=new int[n][n];
		for(int i=0;i<n;i++){
			String s=br.readLine();
			for(int j=0;j<n;j++){
				map[i][j]=s.charAt(j)-'0';
			}
		}
		System.out.println(quadTree(0,0,n));
	}
}