백준 1992 (Java) 쿼드트리

입력

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

출력

영상을 압축한 결과를 출력한다.

예제 입력 1 복사

8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

예제 출력 1 복사

((110(0101))(0010)1(0001))

 

 

해설

size가 2가 될때까지 분할정복을 진행한다.

2가 되었다면 네칸의 합이 4인 경우와 0인 경우는 각각 모든 수가 같은 경우이다.

4또는 0이 아닌 경우는 네칸의 수가 다른 경우이므로 결과값 string으로 바꿔 append한다.

 

size가 2보다 큰 경우, 아직 탐색을 진행해야 한다.

범위 내에서 arr가 서로 같지 않다면 boolean 변수에 체크해둔다.

 

서로 같다면 현재 탐색한 칸들 중 한 칸 (r, c)를 결과값 string에 저장한다.

다르다면 분할정복으로 네 칸을 나눠 탐색을 진행한다.

 

 

 

추가 예제

8
00000000
00000000
00001111
00001111
00011111
00111111
00111111
00111111

(0(0011)(0(0111)01)1)

 

코드

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

public class Main {
    static int n, cnt;
    static int[][] arr;
    static StringBuilder sb = new StringBuilder();

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            for (int j = 0; j < n; j++) {
                arr[i][j] = s.charAt(j) - '0';
            }
        }
        sol(0, 0, n);
        System.out.println(sb);
    }

    static void sol(int r, int c, int size) {
        if (size == 2) {
            int res = arr[r][c] + arr[r][c + 1] + arr[r + 1][c] + arr[r + 1][c + 1];
            if (res == 4) {
                sb.append("1");
            } else if (res == 0) {
                sb.append("0");
            } else {
                sb.append("(" + arr[r][c] + arr[r][c + 1] + arr[r + 1][c] + arr[r + 1][c + 1] + ")");
            }
            return;
        }
        boolean flag = true;
        for (int i = r; i < r + size-1; i++) {
            for (int j = c; j < c + size-1; j++) {
                if (arr[i][j] != arr[i][j + 1]) {
                    flag = false;
                }
                if (arr[i][j] != arr[i+1][j]) {
                    flag = false;
                }
            }
        }
        if (flag) {
            sb.append(arr[r][c]);
        }
        else {
            sb.append("(");
            sol(r, c, size / 2);
            sol(r, c + size / 2, size / 2);
            sol(r + size / 2, c, size / 2);
            sol(r + size / 2, c + size / 2, size / 2);
            sb.append(")");
        }
    }
}

 

그냥 생각없이 푼 것 같은데 풀려서 이상하다...