이 링크에도 잘 설명되어있으니 참고하면 좋다(풀이 이후에 발견했는데, 이런게 있었구나..싶다)
즉 비교적 소수의 경우의 수이므로, 완전탐색이 가능해보인다. BFS로 풀이하여 최댓값을 바로 발견할 수 있을 것이다. 현재 0 위치에서 이동 가능한 상하좌우 퍼즐을 확인하고, 만약 이동 가능하다면 그 위치의 다른 퍼즐과 교환한다. 방문한 적이 없다면 그 방향으로 탐색을 진행한다. 방문 여부는 집합 자료구조를 통해서 매우 쉽게 구현 가능하다.
풀이 코드
from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
nums = ''
for i in range(3) :
num = input().strip().replace(" ","")
for j in range(3) :
if num[j] == '0' :
x, y = j, i
nums += num
q = deque([(0, x, y, nums)])
visited = { nums }
while q :
move, x, y, nums = q.popleft()
if nums == '123456780' :
print(move)
exit()
nums = list(nums)
for k in range(4) :
ax, ay = x + dx[k], y + dy[k]
if -1 < ax < 3 and -1 < ay < 3 :
nums[x + y*3], nums[ax + ay*3] = nums[ax + ay*3], nums[x + y*3]
tmp = ''.join(nums)
if tmp not in visited :
visited.add(tmp)
q.append((move+1, ax, ay, tmp))
nums[x + y*3], nums[ax + ay*3] = nums[ax + ay*3], nums[x + y*3]
print(-1)