[JAVA / 자바] 백준(BOJ) 1992번 - 쿼드트리 (실버 1)

 문제 

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

---

 출력 

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

---

---

 문제 접근 방법 

이 문제는 분할 정복(Divide and Conquer) 문제이다.

 

해당 영역이 모두 같은 숫자가 되면 카운팅 되면서 해당 영역은 더 이상의 분할을 하지 않고 끝나게 되지만, 모두 같은 숫자만 있는 것이 아니라면 해당 영역을 4 분할하여 분할된 각각의 영역에서 다시 같은 숫자만 존재하는지 확인해주어야 한다. 이때, 주의할 점은 영역에 같은 숫자만 존재하지 않아 계속 분할하다가 영역의 크기가 2X2이 된다면 압축이 불가하기 때문에 좌상, 우상, 좌하, 우하의 점 순서대로 괄호 안에 넣어 출력해준다. 이때, 압축이 되면 그냥 숫자만 출력해주면 되지만, 압축이 되지 않는 영역은 압축이 된 점과 비교하기 위해 괄호 안에 넣어 출력한다. 따라서 압축이 안된 횟수만큼 괄호의 개수가 늘어나는 것이다.

 

boolean isEqual()

현재 영역에 저장된 숫자가 모두 같은 숫자인지 판단하여 영역에 저장된 숫자가 동일하면 True 반환, 그렇지 않으면 False를 반환해주는 함수이다.

 

void zip()

변수로 받은 영역이 압축이 가능한지 isEqual 함수로부터 확인받아 압축이 가능하면 바로 출력해주고, 그렇지 않으면 여는 괄호를 출력하고 해당 영역을 다시 4 분할하여 각각의 영역을 zip함수를 재귀 호출하고 위 과정을 반복한 후 닫는 괄호를 출력한다. 이때, 영역의 크기가 2X2라면 압축이 안 되는 점이기 때문에 좌상, 우상, 좌하, 우하의 점 순서대로 괄호 안에 넣어 출력해준다.

---

 JAVA 코드 풀이 

 코드 실행 결과 

---

 후기 

분할 정복 문제 치고 패턴이 단순해서 로직을 생각하는데 크게 오래 걸리지는 않았다. 그래도 다른 문제에 비해 분할 정복 문제를 푸는 시간이 보다 오래 걸리는 감이 없지 않아 있다. 좀 더 노력해야겠다.

 

 ▼ 이번 문제와 유사한 문제 ▼ 

[JAVA / 자바] 백준(BOJ) 2630번 - 색종이 만들기 (실버 3)

[JAVA / 자바] 백준(BOJ) 1780번 - 종이의 개수 (실버 3)

---

 문제 원본 

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

 알고리즘 분류 

• 분할 정복
• 재귀