[JAVA/자바 1992 백준] 쿼드트리

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

 

1992번: 쿼드트리

풀이

find 부분이 중요합니다.

다른분들은 파라미터 3개로 쓴 사람도 있는데,

풀다가 헷갈려서 5개로 나눠서 썼습니다.

분할정복 문제이므로, 

label을 처음 사용해서 해결 가능한 문제인지 판단하고, 할수없으면 break 한뒤 1,2,3,4분면으로 나눠서 재귀적으로 돌립니다.

가능하다면 flag 불린값을 바꿔주고, stat~end까지 출력해줍니다.

import java.awt.Label;
import java.io.*;
import java.util.*;
public class Main {

	static int[][] map;
	static StringBuilder sb=new StringBuilder();
	
	public static void main(String[] args)throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		//map 크기 선언
		map=new int[n][n];
		// 값 넣어주기
		for(int i=0;i<n;i++) {
			String tmp=br.readLine();
			for(int j=0;j<n;j++) {
				map[i][j]=tmp.charAt(j)-'0';
			}
		}
		// size,x_start,x_end,y_start,y_end
		find(n,0,n,0,n);
		System.out.println(sb);
	}
	// size를 줄여가면서 조건 맞춰주기.
	static void find(int size,int x_start,int x_end,int y_start,int y_end) {

		boolean flag=true;
		int tmp=map[x_start][y_start];
		label :for(int i=x_start;i<x_end;i++) {
			for(int j=y_start;j<y_end;j++) {
				if(map[i][j]!=tmp) {
					flag=false;
					break label;
				}
			}
		}
		if(flag==true) {
			sb.append(map[x_start][y_start]);
			return;
		}
		else {
			//1사분면
			sb.append('(');
			find(size/2,x_start,x_start+size/2,y_start,y_start+size/2);
			//2사분면
			find(size/2,x_start,x_start+size/2,y_start+size/2,y_end);
			//3사분면
			find(size/2,x_start+size/2,x_end,y_start,y_start+size/2);
			//4사분면
			find(size/2,x_start+size/2,x_end,y_start+size/2,y_end);
			sb.append(')');
		}
	}

}

x,y의 start,end값이 헷갈린 문제..

비슷한 문제 추천해드릴게용

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

1074번: Z