문제
흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(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의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.
출력
영상을 압축한 결과를 출력한다.
코드
#include <iostream> #include <string> using namespace std; int N; string Map[64]; // 주어진 범위가 모두 0인지 확인한다. bool IsAllZero(int r, int c, int size) { for (int i = r; i < r + size; ++i) { for (int j = c; j < c + size; ++j) { if (Map[i][j] != '0') return false; } } return true; } // 주어진 범위가 모두 1인지 확인한다. bool IsAllOne(int r, int c, int size) { for (int i = r; i < r + size; ++i) { for (int j = c; j < c + size; ++j) { if (Map[i][j] != '1') return false; } } return true; } string QuadTree(int r, int c, int size) { // 모두 같은 숫자인지 확인한다. if (IsAllZero(r, c, size)) return "0"; if (IsAllOne(r, c, size)) return "1"; // 같은 숫자가 아니라면 // 크기를 반으로 나눠 4등분한다. size /= 2; return "(" // 좌상단 + QuadTree(r, c, size) // 우상단 + QuadTree(r, c + size, size) // 좌하단 + QuadTree(r + size, c, size) // 우하단 + QuadTree(r + size, c + size, size) + ")"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> N; for (int i = 0; i < N; ++i) cin >> Map[i]; cout << QuadTree(0, 0, N); } |
using System; using System.Text; namespace Csharp { class Program { static int N; static string[] Map; static StringBuilder Output = new StringBuilder(); static void Main(string[] args) { N = Convert.ToInt32(Console.ReadLine()); Map = new string[N]; for (int i = 0; i < N; ++i) Map[i] = Console.ReadLine(); QuadTree(0, 0, N); Console.Write(Output); } static bool IsSame(int r, int c, int size) { char value = Map[r][c]; for (int i = r; i < r + size; ++i) { for (int j = c; j < c + size; ++j) { if (Map[i][j] != value) return false; } } return true; } static void QuadTree(int r, int c, int size) { if (IsSame(r, c, size)) Output.Append(Map[r][c]); else { size /= 2; Output.Append("("); QuadTree(r, c, size); QuadTree(r, c + size, size); QuadTree(r + size, c, size); QuadTree(r + size, c + size, size); Output.Append(")"); } } } } |
from sys import stdin input = stdin.readline N = int(input()) Map = [ input() for i in range(N) ] def isSame(r, c, size): for i in range(r, r + size): for j in range(c, c + size): if Map[r][c] != Map[i][j]: return False return True def quadtree(r, c, size): if isSame(r, c, size): return Map[r][c] size //= 2 return '(' + quadtree(r, c, size) + quadtree(r, c + size, size) + quadtree(r + size, c, size) + quadtree(r + size, c + size, size) + ')' print(quadtree(0, 0, N)) |
복기
코드로 어떻게 구현할건지를 좀 더 많이 고찰해야겠다.