여덟 퍼즐

[!h]

왼쪽에는 첫 번째 예제의 시작 상태가 있다. 화살표는 첫 번째 이동을 나타낸다. 가운데 그림은 첫 번째 이동 후의 상태를 보여 주며, 화살표들은 오른쪽에 표시된 최종 상태에 도달하기 위해 수행해야 하는 나머지 일곱 번의 이동을 나타낸다.

여덟 퍼즐은 더 잘 알려진 열다섯 퍼즐의 동생 격인 퍼즐로, 틀 안에 있는 여덟 개의 정사각형 타일로 이루어진다. 타일에는 $1$부터 $8$까지 번호가 매겨져 있다. 틀에는 $3\cdot3=9$개의 타일이 들어갈 자리가 있으므로 빈칸이 하나 있다. 한 번의 이동은 빈칸에 인접한 타일을 빈칸의 위치로 미는 것이다. 시작 상태가 주어졌을 때, 위 그림의 오른쪽에 표시된 정렬된 최종 상태에 도달하는 데 필요한 최소 이동 횟수를 계산하는 프로그램을 작성한다.

팁: 임의의 상태는 풀 수 없거나(테스트 케이스에는 이러한 경우가 없다) 최대 31번의 이동으로 풀 수 있다.

점수

여러 테스트 케이스 그룹으로 해답을 평가한다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ | $40$ | 최대 5번의 이동을 사용하는 해가 존재한다.

$2$ | $60$ | 추가 제한이 없다.

입력은 $9$개 위치 각각에 놓인 타일의 번호 또는 빈칸을 나타내는 $0$을 포함하는 한 줄로 이루어진다. 이는 $9$개의 정수로 이루어진 한 줄로 주어지며, 수들은 일반적인 ``읽는 순서''(맨 윗줄부터, 왼쪽에서 오른쪽으로)로 주어진다. $0$부터 $8$까지의 각 수는 정확히 한 번씩 등장한다. 주어지는 테스트 케이스에서는 항상 최종 상태에 도달할 수 있다.

정수 하나를 출력한다. 주어진 상태에서 최종 상태에 도달하는 데 필요한 최소 이동 횟수이다.