스텝 스텝 에볼루션

일본의 게임 회사가 리듬 게임 스텝 스텝 에볼루션을 만들었다. 플레이어는 댄스 발판 위에 서서, 화면을 따라 올라오는 화살표에 맞춰 발판을 밟는다.

이 게임에는 위, 오른쪽 위, 오른쪽, 오른쪽 아래, 아래, 왼쪽 아래, 왼쪽, 왼쪽 위의 여덟 방향이 있다. 화살표는 화면 아래에서 위로 올라오고, 화면 위쪽에 고정된 화살표와 겹치는 순간 플레이어는 그 방향의 발판을 밟는다.

그림 1: 스텝 스텝 에볼루션의 댄스 발판

플레이하는 동안 다음 규칙을 지킨다.

• 플레이가 시작된 뒤에는 화살표 데이터가 요구하지 않은 발판을 밟지 않는다.
• 발은 마지막으로 밟은 발판 위에 그대로 머물고, 다음 발판을 밟을 때까지 움직이지 않는다.
• 왼발은 오른발이 놓인 발판보다 오른쪽에 있는 발판을 밟지 않는다. 반대로 오른발은 왼발이 놓인 발판보다 왼쪽에 있는 발판을 밟지 않는다.

발판의 좌우는 열로 비교한다. 왼쪽 위, 왼쪽, 왼쪽 아래가 왼쪽 열이고, 위와 아래가 가운데 열이며, 오른쪽 위, 오른쪽, 오른쪽 아래가 오른쪽 열이다. 열이 더 오른쪽에 있을 때만 그 발판이 오른쪽에 있다고 보므로, 같은 열에 있는 두 발판은 서로 왼쪽도 오른쪽도 아니다.

그림 2: 올바른 발놀림과 규칙을 어기는 발놀림

그림 2에서 첫 번째(왼발이 왼쪽, 오른발이 아래)와 두 번째(왼발이 왼쪽 아래, 오른발이 왼쪽 위)는 올바르다. 세 번째(왼발이 오른쪽, 오른발이 아래)는 규칙을 어긴다.

플레이를 시작할 때 왼발과 오른발은 어느 발판에나 올려놓을 수 있고, 첫 화살표는 왼발로 밟아도 되고 오른발로 밟아도 된다.

실력 있는 플레이어는 왼발과 오른발을 번갈아 쓰는 자연스러운 발놀림(natural footstep style)으로 플레이한다. 화살표 배열이 어려우면 이 방식을 어길 수밖에 없을 때가 있다. 화살표 배열이 주어질 때, 가장 잘 플레이했을 때 연속한 두 화살표를 같은 발로 밟는 횟수의 최솟값을 구하라.

입력은 여러 개의 데이터 집합으로 이루어진다. 각 데이터 집합은 화살표 배열이 적힌 한 줄이다. 각 방향은 1부터 9까지의 숫자 중 5를 제외한 숫자로 적고, 배치는 숫자판과 같다. 7, 8, 9는 왼쪽 위, 위, 오른쪽 위이고, 4와 6은 왼쪽과 오른쪽이며, 1, 2, 3은 왼쪽 아래, 아래, 오른쪽 아래다.

그림 3: 방향 화살표에 대응하는 숫자

배열의 길이는 1 이상 100000 이하다. 한 배열 안에서 같은 방향이 연속해 나오는 일은 없다. # 한 글자만 있는 줄이 입력의 끝을 나타낸다.

각 데이터 집합마다 가장 잘 플레이했을 때 연속한 두 화살표를 같은 발로 밟는 횟수의 최솟값을 한 줄에 출력한다.