체인 코드

흑백(이진) 이미지에서 서로 연결된 검은 픽셀들의 집합은 전경(물체)으로, 흰 픽셀들은 배경으로 볼 수 있다. 연결된 검은 픽셀 집합은, 임의의 한 경계 픽셀에서 시작해 경계에 있는 픽셀들의 위치를 반시계 방향으로 나열하면 완전히 기술할 수 있다. 위치를 그대로 저장하는 대신, 각 경계 픽셀에서 다음 경계 픽셀로 가는 방향만 저장한다. 이렇게 얻은 방향의 나열을 그 물체의 체인 코드라고 하며, 체인 코드는 물체의 모양을 정확히 나타내면서도 물체의 위치와는 무관하다.\n\n한 픽셀에서 인접한 픽셀로 갈 수 있는 방향은 8가지다. 번호를 붙이는 방식은 약속이며, 방향 0은 오른쪽, 방향 2는 바로 위, 방향 1은 0과 2를 이등분하는 45° 방향이고, 이후 반시계 방향으로 이어진다. 전체 약속은 다음과 같다.\n\n\n3 2 1\n4 . 0\n5 6 7\n\n\n여기서 .는 현재 픽셀이다. 즉 0 = 오른쪽, 1 = 오른쪽 위, 2 = 위, 3 = 왼쪽 위, 4 = 왼쪽, 5 = 왼쪽 아래, 6 = 아래, 7 = 오른쪽 아래이다.\n\n모든 정수 좌표마다 픽셀이 하나씩 있다고 할 때, 두 검은 픽셀은 서로의 거리의 제곱이 2 이하이면(즉 상하좌우 또는 대각선으로 맞닿아 있으면) 인접했다고 한다. 두 픽셀은 인접한 픽셀들의 경로로 이어질 수 있으면 연결되었다고 하고, 연결 영역이란 모든 픽셀이 서로 연결된 검은 픽셀들의 집합이다. 어떤 영역의 경계 픽셀은, 상하좌우 네 방향의 이웃 중 검은색이 아닌 것이 하나라도 있는 영역 내부의 픽셀이다. 이 문제에서 영역에는 구멍이 없다고 가정하므로, 경계는 정확히 하나뿐이다.\n\n체인 코드는 임의의 경계 픽셀에서 시작할 수 있다. 현재 픽셀에서 반시계 방향으로 다음 경계 픽셀을 찾아 그 방향(0–7)을 출력에 덧붙이고 그 픽셀로 이동하는 과정을 반복한다. 다시 시작 픽셀로 돌아오면 체인 코드가 완성된다. 둘레나 넓이(영역에 속한 픽셀의 개수) 같은 모양 관련 값은 체인 코드만으로 바로 계산할 수 있다. 체인 코드만 주어졌을 때 연결 영역의 넓이를 구하는 프로그램을 작성하라.

입력은 한 줄에 하나씩 주어지는 여러 개의 체인 코드로 이루어진다. 각 체인 코드는 숫자 0–7로 이루어지며 길이는 최대 1,000,000자다. 모든 체인 코드는 유효한 영역을 나타내며, 그 경계는 자기 자신과 교차하지 않는다. 입력은 파일의 끝에서 종료된다.

각 체인 코드에 대해 그 영역의 넓이(영역에 속한 픽셀의 개수)를 한 줄에 하나씩 출력한다.

체인 코드가 나타내는 경계는 픽셀 중심들을 잇는 닫힌 경로이며, 방향 0/2/4/6은 상하좌우로 한 칸, 방향 1/3/5/7은 대각선으로 한 칸 움직인다. 영역에 구멍이 없으므로 이 경로는 하나의 단순 폐곱선이 되고, 이미지 전체를 복원하지 않고도 이 경로만으로 (경계 픽셀을 포함한) 영역 내부의 픽셀 개수를 구할 수 있다.