Menu

Subscribe

[종만북]7.분할 정복-쿼드 트리 뒤집기

Donghoon Kang on Algorithm

문제

출처 : https://www.algospot.com/judge/problem/read/QUADTREE

대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2N × 2N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다.

  • 이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 b가 됩니다.
  • 이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 w가 됩니다.
  • 모든 픽셀이 같은 색이 아니라면, 쿼드 트리는 이 그림을 가로 세로로 각각 2등분해 4개의 조각으로 쪼갠 뒤 각각을 쿼드 트리 압축합니다. 이때 전체 그림의 압축 결과는 x(왼쪽 위 부분의 압축 결과)(오른쪽 위 부분의 압축 결과)(왼쪽 아래 부분의 압축 결과)(오른쪽 아래 부분의 압축 결과)가 됩니다. 예를 들어 그림 (a)의 왼쪽 위 4분면은 xwwwb로 압축됩니다.

그림 (a)와 그림 (b)는 16×16 크기의 예제 그림을 쿼드 트리가 어떻게 분할해 압축하는지를 보여줍니다. 이때 전체 그림의 압축 결과는 xxwww bxwxw bbbww xxxww bbbww wwbb가 됩니다.

쿼드 트리로 압축된 흑백 그림이 주어졌을 때, 이 그림을 상하로 뒤집은 그림 을 쿼드 트리 압축해서 출력하는 프로그램을 작성하세요.

입력

첫 줄에 테스트 케이스의 개수 C (C≤50)가 주어집니다. 그 후 C줄에 하나씩 쿼드 트리로 압축한 그림이 주어집니다. 모든 문자열의 길이는 1,000 이하이며, 원본 그림의 크기는 220 × 220 을 넘지 않습니다.

출력

각 테스트 케이스당 한 줄에 주어진 그림을 상하로 뒤집은 결과를 쿼드 트리 압축해서 출력합니다.

풀이(나의 풀이)

분할정복 알고리즘의 경우, 7장에서 배웠던 완전탐색 알고리즘처럼 일반적인 재귀호출처럼 문제를 한조각씩 나누어 해결하는것이 아닌, 거의 균등한 조각들로 나누는 것이 핵심이라고 볼 수 있다. 이 문제의 경우도 쿼드 트리의 구조에서 문자열을 4부분으로 균등하게 쪼개어 더이상 쪼개질 수 없는 문자인 w와 b 까지 나누도록 설계하여야 한다. 내가 생각한 알고리즘의 재귀함수 설계는 다음과 같다.

  1. 매개변수로 받은 문자열이 더이상 쪼갤수 없는 문자(w,b)일 때 그 문자를 출력하고, 아닌 경우 아래 과정을 수행한다.
  2. 쪼개진 문자열 4조각을 저장할 배열을 선언하고, 문자열을 알맞은 크기로 4조각으로 분할한다.
  3. 분할한 각 조각에 대해 해당 함수를 재귀적으로 호출하여 각 조각의 재배열을 수행한다.
  4. 최종적으로 4조각의 순서를 (0,1,2,3) 순에서 (2,3,0,1)로 재배열하여 출력한다.

풀이의 핵심은 문자 x를 알맞게 인식하여 문자열을 4조각으로 적절하게 쪼개는 과정이 중요하다.

static String Reverse(String s) {
		if (s.length() == 1)
			return s;

		String[] S = new String[4];
		int idx = 0;
		int start_idx = 1;
		int end_idx = 1;

		while (start_idx < s.length()) {
			int x_idx = start_idx;
			while(x_idx<=end_idx) {
				if (s.charAt(x_idx) == 'x') {
					end_idx += 4;
				}	
				x_idx++;
			}
			S[idx++] = s.substring(start_idx, ++end_idx);	
			start_idx = end_idx;
		}
		for(int i=0;i<S.length;i++) {
			S[i] = Reverse(S[i]);
		}

		String out = "x"+ S[2] + S[3] + S[0] + S[1];
		return out;
	}

Reverse함수는 매개변수로 입력받은 문자 s를 4조각으로 분할하여 재배열을 수행하고 결과를 출력하는 함수이다. 기저 사례로 입력받은 문자가 w,b일 때, 즉 길이가 1인 문자는 그대로 출력하고, 분할할 수 있는 문자에 대해서는 분할과 재배열을 수행한다. 이 때, 각각의 조각을 분할하는 과정에서 문자 x를 포함하는 압축된 문자를 잘라내는 과정은 분할할 조각 내에 x가 포함될 때 마다 끝부분의 인덱스값이 4씩 증가하므로, 이를 판별하여 부분 문자열의 적절한 시작위치와 종료위치를 설정하여 분할한다. 이 때, 재배열이 수행되는 문자열은 기저사례가 아닌, x로 시작하는 문자이므로 첫 문자 x 뒷부분에 대해 위의 과정을 수행하도록 하며, 재배열이 완료되었을 때 최종 결과물의 맨 앞에 다시 x를 추가하도록 한다.

이 경우, 문자열의 길이에 따라 분할하는 과정을 재귀적으로 수행하므로, 함수의 호출 횟수는 문자열의 길이 n에 비례하므로 시간복잡도는 O(n)이 된다.

풀이(책 참고)

책을 참고해보니, 위의 재귀함수는 아래와 같이 훨씬 간단하게 구현할 수 있음을 확인하였다.

static String Reverse(String s) {
		++idx;
		char c = s.charAt(idx);
		if(c=='b' || c=='w')
			return c+"";
		String upperLeft = Reverse(s);
		String upperRight = Reverse(s);
		String lowerLeft = Reverse(s);
		String lowerRight = Reverse(s);
		
		return "x"+lowerLeft+lowerRight+upperLeft+upperRight;
}

기존 나의 풀이에서 전체 조각을 4조각으로 나눌 때, x성분을 검사하기 위해 반복문을 사용하여 비교적 복잡한 구조를 설계하였는데, 위의 코드에서는 문자열의 각 성분을 검사하는 인덱스값 idx를 재귀함수 외부의 전역변수로 선언하여, 순서대로 Reverse함수를 호출할 때마다 다음 인덱스를 검사하게끔 구현하여 훨씬 더 간단하게 각 성분을 검사하는 것을 알 수 있다. 즉, 함수가 호출될 때 마다 전역변수 idx값을 증가시켜 다음 문자를 검사하게 하며, 이 때의 문자가 w와 b일 경우 출력하고, 아닌 경우는 4조각으로 나눠야 하므로 다음 인덱스부터 다시 4조각으로 나누는 과정을 수행한다.

이 경우, 함수의 호출에 따라 주어진 문자열의 한 글자씩을 사용하므로 함수가 호출되는 횟수는 문자열의 길이 n에 비례하여 O(n)이 된다.