1998번 - 이미지 압축 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 369 | 80 | 45 | 20.270% |
문제
흰색과 검은색으로 이루어진 이미지는 쿼드트리를 이용하여 표현할 수 있다. 쿼드트리의 루트는 이미지의 전체를 나타낸다. 만약 전체 이미지가 한 색깔로 이루어져 있으면, 그 색깔에 해당하는 정점을 루트로 한다. 그 외의 경우에는 그림을 넷으로 나누고, 각각의 나눠진 그림을 루트의 네 자식 정점으로 표현하면 된다. 이때 첫 번째 자식이 왼쪽 위의 그림을, 두 번째 자식이 오른쪽 위의 그림을, 세 번째 자식이 왼쪽 아래의 그림을, 네 번째 자식이 오른쪽 아래의 그림을 표현하게 된다. 각각의 작은 이미지를 표현할 때도 같은 방법을 재귀적으로 적용한다.
위의 예는 4×4 크기의 이미지와 그에 해당하는 쿼드트리이다. 위의 예에서는 이미지의 크기(사각형의 변의 길이)가 2의 k승이라서 상관이 없었지만, 그 외의 경우에는 문제가 된다. 만약에 이미지의 크기가 2의 k승이 아닐 경우에는, 이미지의 크기를 오른쪽과 아래쪽으로 가장 가까운 2의 k승으로 늘린 뒤, 흰색으로 나머지 공간을 채우면 된다. 이때 이미지가 정사각형 모양이 되도록 한다. 예를 들어 5×13의 이미지는 16×16 크기의 이미지가 되고, 원래의 이미지가 왼쪽 위에 들어가고 나머지 공간은 흰색으로 채우면 된다.
쿼드트리 자체가 이미지를 압축적으로 표현하는 방법이지만, 우리는 압축된 쿼드트리를 이용하여 좀 더 효율적으로 표현하려 한다. 만약 쿼드트리에서 같은 모양의 부분 트리가 여러 개 나올 경우, 이를 한 번만 저장한 뒤 나머지는 포인터로 연결할 수 있다. 위의 예는 다음과 같은 압축된 쿼드트리로 표현할 수 있다.
원래의 쿼드트리는 17개의 정점을 갖지만, 압축된 쿼드트리는 12개의 정점을 갖는다. 12개의 정점을 갖는 압축된 쿼드트리가 몇 개 더 있기는 하지만, 11개 이하의 정점을 갖는 압축된 쿼드트리는 존재하지 않는다. 따라서 위의 경우가 가장 효율적(정점 개수가 최소)이다.
주의할 것은, B나 W로 표현되는 정점은 포인터가 아니가 값 자체이므로 이를 연결할 경우는 압축하는 것이 아니다. 즉, 정점이 하나인 경우(높이가 1인 경우)에는 포인터를 이용하여 연결할 필요가 없다. 또, 실제 이미지의 크기가 다르더라도 트리의 모양이 같다면, 같은 쿼드트리로 표현될 수 있는데, 이런 경우에도 포인터로 연결할 수 있다.
이미지가 주어졌을 때, 쿼드트리의 정점의 개수와 가장 효율적인 압축된 쿼드트리의 정점의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 이미지의 크기를 나타내는 두 정수 n(1 ≤ n ≤ 128), m(1 ≤ m ≤ 128)이 주어진다. 이는 이미지의 크기가 n×m이라는 의미이다. 다음 n개의 줄에는 m개의 숫자로 이미지가 주어진다. 흰색은 0으로, 검은색은 1로 표현된다.
출력
첫째 줄에 쿼드트리의 정점의 개수와 가장 효율적인 압축된 쿼드트리의 정점의 개수를 출력한다.
예제 입력 1
4 4 1011 0111 1010 0111
예제 출력 1
17 12
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호