Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

20. 분할 정복

재귀를 응용하는 알고리즘, 분할 정복을 익혀 봅시다.

Java / Python

2. 쿼드트리

1992번

쿼드트리를 문자열로 바꾸는 문제

이번 문제는 흑백 영상을 압축하여 표현하는 데이터 구조인 쿼드트리를 이용하여 N x N 크기의 영상을 압축한 결과를 출력하는 문제입니다. 저번 색종이 문제와 비슷합니다.

• Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
	
	public static int[][] image;
	public 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());
		
        image = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			String str = br.readLine();
			
			for(int j = 0; j < N; j++) {
				image[i][j] = str.charAt(j) - '0';
			}
		}
		
		QuadTree(0, 0, N);
		System.out.println(sb);
	}
	
	public static void QuadTree(int x, int y, int size) {
		
		if(isPossible(x, y, size)) {    // 압축 가능하면 압축
			sb.append(image[x][y]);
			return;
		}
		
		int newSize = size / 2;	// 압축 불가능 - 사이즈를 절반으로
		
		sb.append('(');	
		
		QuadTree(x, y, newSize);						// 왼쪽 위
		QuadTree(x, y + newSize, newSize);				// 오른쪽 위
		QuadTree(x + newSize, y, newSize);				// 왼쪽 아래
		QuadTree(x + newSize, y + newSize, newSize);	// 오른쪽 아래
		
		sb.append(')');
		
	}	
	
	// 압축이 가능한지 공간을 확인
	public static boolean isPossible(int x, int y, int size) {
		int value = image[x][y];
		
		for(int i = x; i < x + size; i++) {
			for(int j = y; j < y + size; j++) {
				if(value != image[i][j]) {
					return false;
				}
			}
		}
		return true;
	}
}

• Python

import sys
N = int(sys.stdin.readline())
image = [list(map(int,sys.stdin.readline().strip())) for _ in range(N)]

def QuadTree(x, y, n):
    check = image[x][y]
    for i in range(x,x+n):
        for j in range(y,y+n):
            if check != image[i][j]: # 하나라도 다르면
                print('(', end='')
                QuadTree(x,y,n//2) # 1사분면
                QuadTree(x,y+n//2,n//2) # 2사분면
                QuadTree(x+n//2,y,n//2)  # 3사분면
                QuadTree(x+n//2,y+n//2,n//2) # 4사분면
                print(')', end='')
                return
 
    if check == 0:
        print('0',end='')
        return
    else:   
        print('1',end='')
        return

QuadTree(0,0,N)