[백준, JAVA] 1992번 : 쿼드트리

1. 문제

2. 아이디어

• 공백을 기준으로 입력을 받지 않아서, StringTokenzier 활용은 어렵다.
  -> charAt 함수를 활용하고, -'0' 연산으로 int로 바꾸어 준다.

• 예제 출력을 처음 보고 당황했지만, 이해하고 나니 어렵지 않았다.

  인접한 4개의 칸이 모두 같은 숫자이면, 해당 숫자로 표현한다.

  -> 해당 숫자를 StringBuilder를 활용해서 이어붙여야겠다!

• 분할 정복에서 나오는 '작은문제'에 해당하는 답을 ( )로 감싸 주면 된다.

  함수가 호출되는 시점에 유념해서 괄호를 열고 닫아준다.

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static int[][] map;
	public static int one;
	public static int zero;
	public static StringBuilder sb = new StringBuilder();
	
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        map = new int[N][N];
        for (int i = 0; i < N; i++) {

            String str = bf.readLine();
        	for (int j = 0; j < N; j++) {
                map[i][j] = str.charAt(j)-'0';
            }
        }
        
        divide(0, 0, N);
        System.out.println(sb);
    }
    
    public static void divide(int row, int col, int size) {

    	if(colorCheck(row, col, size)) {
    		sb.append(map[row][col]);
    		
    		return;
    	}
    	
    	int newSize = size/2;
    	
    	sb.append('(');
    	divide(row, col, newSize); // 2사분면
    	divide(row, col+newSize, newSize); // 1사분면
    	divide(row+newSize, col, newSize); // 3사분면
    	divide(row+newSize, col+newSize, newSize); // 4사분면
    	sb.append(')');
    }
    
    public static boolean colorCheck(int row, int col, int size) {
    	int color = map[row][col]; // 시작점(원점)의 색
    	
    	for(int i=row; i<row+size; i++) {
    		for (int j = col; j < col+size; j++) {
    			if(map[i][j]!=color) return false; // 시작점의 색이 무엇이든, 같지 않다면 false
			}
    	}
    	
    	return true;
    }
    
}

4. 느낀점

• 문자열 입출력 받기와 StringBuilder 활용을 연습해볼 수 있어서 좋았다.

• 비슷한 유형으로 한 문제 씩 반복해서 풀다보니.. 분할정복 분할정복 완료 ^_^;