from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
g = [list(map(int, input().split())) for _ in range(3)]
q = deque()
g1 = ''
for i in range(3):
for j in range(3):
g1 += str(g[i][j])
if g[i][j] == 0:
fx = i * 3 + j
# (0, 0) = 0 (0, 1) = 1 (0, 2) = 2
# (1, 0) = 3 (1, 1) = 4 (1, 2) = 5
# (2, 0) = 6 (2, 1) = 7 (2, 2) = 8
# 앞에거 곱하기 3해서 뒤에거 더해줌
check = dict()
q.append((0, fx, g1))
ans = -1
check.get(g1)
while q:
cnt, x, l = q.popleft()
if l == '123456780':
ans = cnt
break
x0, y0 = x // 3, x % 3
for d in range(4):
nx, ny = x0 + dx[d], y0 + dy[d]
if nx < 0 or ny < 0 or nx >= 3 or ny >= 3:
continue
new = nx*3+ny
if new > x:
tmp = l[:x] + l[new] + l[x+1:new] + l[x] + l[new+1:]
else:
tmp = l[:new] + l[x] + l[new+1:x] + l[new] + l[x+1:]
if not check.get(tmp):
q.append((cnt + 1, new, tmp))
check[tmp] = 1
print(ans)
bfs로 모든 경우를 탐색. 퍼즐을 문자열 처리해서 구해줌, 행은 몫, 열을 나머지로 이동시켜줌. 리스트로 구현하면 시간초과나서 딕셔너리로 구현해줌