import sys
input = sys.stdin.readline
from collections import deque
dy = [1,-1,0,0]
dx = [0,0,1,-1]
puzzle = ""
for i in range(3):
puzzle += "".join(input().split())
memory = set()
result = -1
dq = deque()
dq.append((puzzle,0))
while dq:
p,cnt = dq.popleft()
if p in memory:
continue
if p == "123456780":
result = cnt
break
memory.add(p)
zero = p.find("0")
y,x = zero//3,zero%3
plist = [[*p[:3]],[*p[3:6]],[*p[6:]]]
for i in range(4):
y1,x1 = y+dy[i],x+dx[i]
if 3>y1>=0 and 3>x1>=0:
plist[y][x] = plist[y1][x1]
plist[y1][x1] = "0"
dq.append((("".join(map(lambda x:"".join(x),plist))),cnt+1))
plist[y1][x1] = plist[y][x]
plist[y][x] = "0"
print(result)
BFS + 백트래킹으로 해결하였다.
기본적인 알고리즘은,
1. deque에 퍼즐의 숫자를 일렬로 나열한 문자열을 저장한다.
2. memory에 현 문자열이 이미 있으면 continue, 없으면 추가한다.
3. 4방향에 대해서 탐사한다.
4. cnt 출력
이때 이 문제를 DFS로 해결하려고 시도하면 틀리게 된다. 왜냐하면 같은 모양을 다른 cnt로 만들 수가 있는데 DFS로 문제를 풀면 더 작은 cnt가 있음에도 불구하고 이미 memory에 해당 문자열이 존재하여 최솟값을 찾을 수 없게 되기 때문이다.
오늘의 교훈) 문제에 따라 BFS, DFS를 신중히 고민하자