[Java+Python]1992번, 쿼드 트리

목차

 

분할 정복 단계

 

[Java+Python]2630번, 색종이 만들기

[Java+Python]1780번, 종이의 개수

[Java+Python]1629번, 곱셈

[Java+Python]11401번, 이항 계수 3

[Java+Python]2740번, 행렬 곱셈

[Java+Python]10830번, 행렬 제곱

[Java+Python]11444번, 피보나치 수 6

[Java+Python]6549번, 히스토그램에서 가장 큰 직사각형

 

문제

 

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 

흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 

쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

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

만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 

이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다.

 

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 

이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다. 

N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

 

 

입력

 

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. 

N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 

두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 

각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

 

출력

 

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

 

풀이

 

직전 문제인 <2630: 색종이 만들기> 문제와 사실상 동일한 문제이다.

 

조건에 따라 사각형을 사등분하고 거기서 다시 조건을 따져보기를 반복하는 문제이니까.

 

물론 출력 부분이 조금 다르긴 하지만, 이 역시 문제에 친절하게 설명되어 있으므로 크게 걱정할 부분은 아니다.

 

문제를 해결하는 알고리즘은 다음과 같다.

 

1. 입력으로 주어진 영상의 한 변의 길이 n을 저장하고 이를 이용해 n x n 이차원 배열(리스트) video를 초기화한다.
2. 정답을 저장할 빈 문자열(자바의 경우 StringBuilder sb, 파이썬의 경우 result)을 생성한다.
3. 재귀함수 quadrant를 호출한다. 해당 함수의 작동 방식은 아래와 같다.
   
   
   1. isSame 메서드를 호출해 현재 분할 영역이 전부 같은 값인지 확인한다.
   2. 전부 같은 값이라면 sb, 혹은 result에 해당 값(0 또는 1)을 저장하고 반환한다.
   3. 같은 색이 아니라면 영상을 문제의 조건에 맞춰 4등분 한 뒤 재귀호출을 하고, 결과의 앞뒤를 괄호로 감싸준다.
   4. 모든 영역이 같은 값을 가질 때까지 반복한다.
4. 저장된 문자열 sb, 혹은 result를 출력한다.

 

Java

 

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

public class Main {

	static int[][] video;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		video = new int[n][n];

		for (int i = 0; i < n; i++) {
			String str = br.readLine();
			for (int j = 0; j < n; j++) {
				video[i][j] = str.charAt(j) - '0';
			}
		}

		quadrant(0, 0, n);
		System.out.println(sb.toString());
	}

	private static void quadrant(int row, int col, int size) {

		if (isSame(row, col, size)) {
			sb.append(video[row][col]);
			return;
		}

		int newSize = size / 2;
		sb.append("(");
		quadrant(row, col, newSize);
		quadrant(row, col + newSize, newSize);
		quadrant(row + newSize, col, newSize);
		quadrant(row + newSize, col + newSize, newSize);
		sb.append(")");
	}

	private static boolean isSame(int row, int col, int size) {

		int color = video[row][col];

		for (int i = row; i < row + size; i++) {
			for (int j = col; j < col + size; j++) {
				if (video[i][j] != color) {
					return false;
				}
			}
		}

		return true;
	}
}

 

Python

 

import sys

n = int(sys.stdin.readline().rstrip())
video = [list(map(int, list(sys.stdin.readline().rstrip()))) for _ in range(n)]
result = ''


def is_same(row, col, size):
    color = video[row][col]
    for i in range(row, row + size):
        for j in range(col, col + size):
            if video[i][j] != color:
                return False
    return True


def quadrant(row, col, size):
    global result

    if is_same(row, col, size):
        result += str(video[row][col])
        return

    new_size = size // 2

    result += '('
    quadrant(row, col, new_size)
    quadrant(row, col + new_size, new_size)
    quadrant(row + new_size, col, new_size)
    quadrant(row + new_size, col + new_size, new_size)
    result += ')'


quadrant(0, 0, n)

print(result)

 

Performance