이미지 분할

의료 영상 회사에 입사했다고 하자. 여러분이 맡은 일은 영상 분석 시스템의 일부로 동작하는 검사 프로그램을 만드는 것이다. X선 장비나 초음파 스캐너처럼 많은 장치가 인체 내부 구조를 촬영한 이미지를 만들어 낸다. 이런 이미지를 자동으로 분석하는 첫 단계는, 비슷한 모양이나 색을 가진 연결된 영역으로 이미지를 나누는 것이다.

여기서 연결이 무엇을 뜻하는지는 작은 예로 설명하는 것이 가장 쉽다. 아래 왼쪽에 6행 10열 크기로 확대한 이미지가 있다. 픽셀의 색은 흰색, 회색, 검은색 세 가지다. 같은 색을 가진 두 픽셀이 가로, 세로 또는 대각선으로 인접해 있으면 같은 영역에 속한다고 본다. 따라서 회색 픽셀 7개는 하나의 연결된 영역을 이룬다. 이 이미지에는 모두 5개의 연결된 영역이 있다. 오른쪽 그림에서는 같은 영역에 속한 픽셀에 같은 번호를 붙였다.

이미지를 살펴보고 영역의 개수를 출력하는 프로그램을 작성하라. 다음 규칙을 추가로 고려해야 한다.

• 이미지는 컬러다. 각 픽셀의 색은 세 정수의 조합 $(R, G, B)$로 기록되며, $R$, $G$, $B$는 0 이상 255 이하의 정수다.
• 실제 이미지에는 정확히 한 가지 색으로만 이루어진 영역이 거의 없으므로, 비슷한 색을 같은 색으로 취급해야 한다. 이를 위해 밴딩(banding)을 사용한다. 각 이미지에는 밴드 크기 $S$가 함께 주어진다. 모든 색 값은 $S$로 나눈 몫(정수 나눗셈)을 밴드 번호로 삼아 변환한다. 예를 들어 $S = 32$이면 $0..31$은 밴드 0, $32..63$은 밴드 1이 된다. 색 $(5, 32, 76)$은 밴드 조합 $(0, 1, 2)$로 바뀐다. 두 색의 밴드 조합이 같으면 같은 색으로 본다.
• 의료 목적에서는 작은 영역을 무시할 수 있다. 각 이미지에는 크기 제한 $L$이 주어지며, 픽셀 수가 $L$개 미만인 영역은 세지 않는다.

입력은 여러 이미지의 나열이다. 각 이미지는 공백으로 구분된 네 정수 $H\ W\ S\ L$ 한 줄로 시작한다. 각각 이미지의 높이, 너비, 밴드 크기, 영역 크기 제한을 뜻한다. $W$와 $H$는 1 이상 1024 이하다. 이어서 $H$개의 픽셀 데이터 줄이 온다. 각 줄에는 연속한 픽셀의 $R$, $G$, $B$ 값을 나타내는 $W$개의 세 값 묶음이 하나의 공백으로 구분되어 들어 있다. 입력의 끝은 네 개의 0이 있는 줄로 표시된다.

각 이미지에 대해, 너무 작아 세지 않는 영역을 제외한 영역의 개수를 한 줄에 출력한다.