[백준] 1992번 쿼드트리 for JAVA 분할정복을 이용한 풀이

문제설명

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(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의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

 

예제입력

8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

 

예제출력

((110(0101))(0010)1(0001))

 

문제풀이

쿼드트리 문제는 전체가 0/1 중 하나의 값으로만 구성되어있는지 확인을 하고, 만약 전체가 하나의 값으로 일치하지 않는다면 영역을 4등분(왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래)하여 앞선 과정을 반복한다.

1. 전체가 통일된 값이 아니라면 4등분으로 구분(Divide)
2. 나뉘어진 작은 영역을 계산(Conquer)
3. 해결된 답을 모으기(Combine)

 

위와 같이, 3단계를 통해 답을 해결할 수 있다.

즉, 이번 문제는 분할정복(divide and conquer) 문제임을 알 수 있다. 

 

Step1

영역을 4등분하기 위해 resize 함수를 선언했다. 

check 함수를 통해 전체가 통일된 값으로 구성되어있는지 확인하고, 참이면 해당 값을 결과값에 추가한다.

만약 거짓이라면 새로운 영역을 나타내기 위해 "(" 추가하고 재귀함수를 이용하여 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래를 resize한다. 여기서 size는 영역이 4등분되기 때문에 "size /. 2" 을 대입한다.

	static void resize(int x, int y, int size) {
		if (check(x, y, size)) {
			sb.append(map[x][y]);
			return;
		}
		sb.append("(");

		resize(x, y, size / 2);
		resize(x, y + size / 2, size / 2);
		resize(x + size / 2, y, size / 2);
		resize(x + size / 2, y + size / 2, size / 2);

		sb.append(")");
	}

 

Step2

step1에서 보았던 check 함수로, 해당 범위가 모두 같은 값으로 구성되어있는지 확인한다. 모두 같은 값이면 true를, 하나라도 다른값이 있다면 false를 return한다.

	static boolean check(int x, int y, int size) {
		int v = map[x][y];

		for (int i = x; i < x+size; i++)
			for (int j = y; j < y+size; j++)
				if (map[i][j] != v)
					return false;
		return true;
	}

Solution

public class Main {

	static String s;
	static StringBuilder sb = new StringBuilder();
	static int N, res, map[][];
	static StringTokenizer st;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		// map 배열 초기화
		for (int x = 0; x < N; x++) {
			s = br.readLine();
			for (int y = 0; y < N; y++) {
				map[x][y] = s.charAt(y) - '0';
			}
		}
		
		resize(0, 0, N);

		bw.write(sb.toString());

		bw.flush();
		bw.close();
		bw.close();
	}

	static boolean check(int x, int y, int size) {
		int v = map[x][y];

		for (int i = x; i < x+size; i++)
			for (int j = y; j < y+size; j++)
				if (map[i][j] != v)
					return false;
		return true;
	}

	static void resize(int x, int y, int size) {
		if (check(x, y, size)) {
			sb.append(map[x][y]);
			return;
		}
		sb.append("(");

		resize(x, y, size / 2);
		resize(x, y + size / 2, size / 2);
		resize(x + size / 2, y, size / 2);
		resize(x + size / 2, y + size / 2, size / 2);

		sb.append(")");
	}
}

 

마치며

분할정복 문제는 어떻게보면 다른 알고리즘 문제보다 쉽게 접근할 수 있는 문제인 것 같다. 앞서 말했던 3단계 1) 작은 영역으로 나누기 2) 나누어진 작은 영역 계산 3) 필요 시, 해결된 답 모으기  에 해당하는 부분을 잘 고민해본다면 알고리즘 구현에 도움이 될 것 같다.

비슷한 문제로 프로그래머스 - 쿼드압축 후 개수 세기, 백준-Z, 백준-별찍기10, 백준-숫자카드2 를 추천한다.

 

문제 바로가기

1992번: 쿼드트리