목록쿼드트리 (1)
블로그 옮겼습니다
BOJ 1998번 이미지 압축
이 문제는 흔히 가로외 세로의 길이가 같은 격자판에서 각 칸이 검은색 또는 흰색으로 이루어져 있을때 자식이 4개이거나 0개인 트리로 격자를 표현하는 '쿼드 트리' 라는 개념의 변형 문제이다. 격자가 주어졌을때 이 격자를 가장작은 정사각형모양으로 키우고 새로생긴 격자를 흰색으로 채운 뒤 쿼드트리의 노드의 개수를 구하는 것이 첫번째 요구되어지는 것이고 그다음엔 압축된 쿼드트리의 노드 수를 구해야 하는데 압축을 하는 방법은 공통된 서브 트리들을 딱 하나만남겨서 공유하는 것이다. 이렇게 할때 최소한의 노드 수를 사용하도록 압축했을 때의 노드의 수를 구하는 것이 두번째 요구되어지는 답이다. 우선 복잡도 계산을 위해 총 노드 수의 상한을 계산해보자. 격자의 가로 세로 길이는 128이 최대이기 때문에 쿼드트리의 높이..
Algorithm/Problem Solving
2017. 4. 5. 07:04