![[1992번] 쿼드트리](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fuof9I%2FbtqwAk83G8u%2FknvFBm7ElUzz3YxGCBNCjk%2Fimg.png)
반응형
1992번: 쿼드트리
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.
www.acmicpc.net
분할 정복(Divide-&-Conquer)의 대표적인 문제 중 하나입니다.
이전에 포스팅했던 [2630번] 색종이 만들기와 같은 알고리즘을 씁니다.
다만 이번에는 개수를 세는 것이 아니라
4등분 후 해당 면이 모두 같은 숫자로 채워져 있다면 그 숫자가 그 분면을 대표하는 숫자라 할 수 있겠죠.
그래서 그 숫자로 압축을 하는 것입니다.
재귀 함수를 쓰고 출력 형식만 잘 지켜주면 쉽게 풀 수 있습니다.
반응형