📖Problem

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

주어진 영상이

• 모두 0으로만 되어 있으면 → 압축결과 “0”
• 모두 1로만 되어 있으면 → 압축결과 “1”
• 해당 사항 없이 0과 1이 섞여 있을 경우 → 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 4개의 방향으로 나누어 다시 탐색하고 결과 도출

문제에 주어진 배열은 빨간 선과 같이 구분하여 나타낼 수 있다.

결과: “(0(0011)(0(0111)01)1)”

🔍Intuition

<aside> 📌 분할 정복 (divide and conquer)

</aside>

• 기법의 이름 그대로 큰 문제를 분할하여, 작은 문제들(Sub problems)로 나눈 뒤 그 결과들을 합쳐 기존의 큰 문제를 해결해나가는 기법
• 분할정복의 경우 재귀적으로 해결하는 방식이 가장 많이 사용되곤 한다.
• 대부분 재귀 함수를 통해 구현이 되며 메모리 제한이 없다면 비교적 빠르게 문제를 해결할 수 있다. 이는 재귀 함수를 통해 거의 절반으로 분리하기 때문에 가능하다.

이 문제는 #2630. 색종이 만들기 문제랑 비슷하게 접근하면 된다.