[Java] 1992번. 쿼드트리 (#깊이 우선탐색)

문제링크 : https://www.acmicpc.net/problem/1992

출력형식 때문에 어려울 것이라 생각했으나 생각보다 쉬운 문제

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

public class Main {
    public static int n; //영상 한변 길이
    public static boolean[][] map; //영상 맵
    public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new boolean[n+1][n+1];
        //입력
        for(int i = 1 ; i <= n ; i++){
            String line = br.readLine();
            for( int j = 1 ; j <= n ; j++){
                if(line.charAt(j-1) == '1') map[i][j] = true;
            }
        }
        //실행
        run(1,1,n);
        //출력
        System.out.println(sb.toString());
    }
    
	//압축가능한지 판단하고 아니면 -1, 압축가능하면 해당 값(1 또는 0)을 리턴
    public static int isComppressable(int startX, int startY, int length){
        for(int i = startX ; i < startX+length ; i++){
            for(int j = startY ; j < startY+length ; j++){
                if(map[i][j] != map[startX][startY]) return -1;
            }
        }
        return map[startX][startY]?1:0;
    }
    
	//쿼드트리 압축처리 DFS(압축가능하면 해당숫자, 아니면 DFS)
    public static void run(int startX, int startY, int length){
        switch (isComppressable(startX, startY, length)){
            case -1:
                sb.append("(");
                run(startX, startY, length/2);
                run(startX, startY + length/2, length/2);
                run(startX + length/2, startY, length/2);
                run(startX + length/2, startY + length/2, length/2);
                sb.append(")");
                break;
            case 0:
                sb.append("0"); break;
            case 1:
                sb.append("1");
        }
    }

}