백준 1525 퍼즐

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로 모든 경우를 탐색. 퍼즐을 문자열 처리해서 구해줌, 행은 몫, 열을 나머지로 이동시켜줌. 리스트로 구현하면 시간초과나서 딕셔너리로 구현해줌