[코딩테스트/백준 알고리즘] 1992번 - 쿼드트리 (Java, 자바 풀이)

문제

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

1992번: 쿼드트리

---

문제 설명

---

문제 풀이

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

1780번: 종이의 개수

이 문제랑 풀이 방식이 비슷했다.

재귀 호출을 통해 해결할 수 있는 문제다.

---

코드

import java.io.*;
import java.util.*;

class Main {
    static String[] map;
    static StringBuilder result = new StringBuilder();


    //압축
    static void zip(int row, int col, int size){
    
    	//사이즈가 1일때
        if(size == 1) {
            if(map[row].charAt(col) == '1')
                result.append(1);
            else
                result.append(0);
        }
        else {
            boolean flag = true;
            char ch = map[row].charAt(col);
            for(int i = row; i < row + size; i++) {
                for(int j = col; j < col + size; j++){
                    if(ch != map[i].charAt(j)) {
                        flag = false;
                        break;
                    }
                }
            }
	    //압축이 가능하면
            if(flag) {
                result.append(ch);
            }
            else {
                result.append("(");
                zip(row, col, size / 2);
                zip(row, col + size / 2, size / 2);
                zip(row + size / 2, col, size / 2);
                zip(row + size / 2, col + size / 2, size / 2);
                result.append(")");
            }
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        map = new String[N];

	//입력
        for(int i = 0; i < N ;i++) {
            map[i] = br.readLine();
        }

        zip(0, 0, N);
	//출력
        System.out.println(result);
    }
}