틀린 내 코드..

import sys
from collections import deque

sys.stdin = open('input.txt', 'rt')
input = sys.stdin.readline

puzzle = []
answer = [[1,2,3],[4,5,6],[7,8,0]]
queue = deque()

dx = [0,0,1,-1]
dy = [-1,1,0,0]

visited = [[False] * 3 for _ in range(3)]

for i in range(3):
    puzzle.append(list(map(int, input().split())))

def bfs():
    count = 0

    while queue:
        y, x = queue.popleft()
        print(puzzle)

        if puzzle == answer:
            print(count)
            break

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if 0 <= ny < 3 and 0 <= nx < 3 and visited[ny][nx] == False:
                puzzle[ny][nx], puzzle[y][x] = puzzle[y][x], puzzle[ny][nx]
                visited[ny][nx] = True
                count += 1
                queue.append([ny, nx])

    print(-1)


for y in range(3):
    for x in range(3):
        if puzzle[y][x] == 0:
            queue.append([y, x])
            visited[y][x] = True

bfs()

단순히 빈칸을 이동시켜서 리스트가 정렬될 때, 출력해주면 될 줄 알았는데 실패했다.

정답 코드

from collections import deque

def bfs():
    while q:
        d = q.popleft()
        if d == 123456789: # 순서대로 정렬이 되어 있을 경우 dist[d] (거리) 출력
            print(dist[d])
            return
        s=str(d) # 문자로 바꿈
        zero=s.find('9') # 문자열에서 9를 찾아서 인덱스 반환
        # x는 행 y는 열
        x,y = zero//3, zero%3 # 문자열이므로 
        for dx, dy in (1,0), (-1,0), (0,1), (0,-1): # 동서남북으로 돌면서
            nx, ny = x+dx, y+dy
            if 0<=nx<3 and 0<=ny<3: # 범위 조건 안에 있다면
                k = nx*3+ny # 동서남북 바꿀 위치 (문자열이므로)
                ns = list(s) # 기존 문자열을 리스트로 다시 변환
                ns[k], ns[zero] = ns[zero], ns[k] # 위치 변경
                nd = int(''.join(ns)) # 숫자로 변경
                if not dist.get(nd): # nd에 대한 딕셔너리 키가 없는 경우
                    dist[nd]=dist[d]+1 # 이동 거리에 1을 추가
                    q.append(nd) # 큐에 추가
    print(-1)


q = deque()
dist = {} # 딕셔너리를 사용
puzzle = [list(map(int, input().split())) for _ in range(3)]
m=0
for i in range(3):
    for j in range(3):
        n = puzzle[i][j]
        if n==0: # 시작 위치일 경우
            n=9 # n을 9로 바꿔준다.
        m = m*10 + n
q.append(m)
dist[m]=0 # 현재 0이 있는 위치의 dist를 0으로 초기화
bfs()