[BOJ] 1992 쿼드트리 - JAVA

1. 문제

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

1992번: 쿼드트리

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다.

만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

---

2. 풀이

주어진 영상 범위를 체크하는 메서드.

만약 범위에 있는 데이터가 모두 같다면 true, 아니라면 false를 반환한다.

public static boolean checkVideo(int n,int i,int j){
    int check = video[i][j];
    for(int y=i;y<i+n;y++){
        for(int x=j;x<j+n;x++){
            if(check!=video[y][x]) return false;
        }
    }
    return true;
}

 

영상을 압축하는 메서드

영상 범위가 모두 같거나 n==1이라면 첫번째 영상데이터만 StringBuilder에 저장하고 끝낸다.

아니라면 범위를 4개로 나누어 재귀호출한다. 재귀호출하기 전과 후에 각각 괄호를 하나씩 저장한다.

public static void zipVideo(int n,int i,int j){
    if(n==1 || checkVideo(n,i,j)) {
        sb.append(video[i][j]);
        return;
    }

    sb.append("(");

    int halfN = n>>1;
    zipVideo(halfN,i,j);
    zipVideo(halfN,i,j+halfN);
    zipVideo(halfN,i+halfN,j);
    zipVideo(halfN,i+halfN,j+halfN);

    sb.append(")");

}

 

메인

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

    video = new int[N][N];

    for (int i = 0; i < N; i++) {
        String line = in.readLine();
        for (int j = 0; j < N; j++) {
            video[i][j] = line.charAt(j) - '0';
        }
    }

    zipVideo(N,0,0);
    System.out.println(sb);

}

---

3. 결과