class Solution:

    def slidingPuzzle(self, board: List[List[int]]) -> int:

        visit = {'123450': 0}

        queue = deque(['123450'])

        while queue:

            cur = queue.popleft()

            idx = cur.index('0')

            if idx % 3 != 2:

                s = list(cur)

                s[idx], s[idx+1] = s[idx+1], s[idx]

                nxt = ''.join(s)

                if nxt not in visit:

                    queue.append(nxt)

                    visit[nxt] = visit[cur] + 1

            if idx % 3 != 0:

                s = list(cur)

                s[idx], s[idx-1] = s[idx-1], s[idx]

                nxt = ''.join(s)

                if nxt not in visit:

                    queue.append(nxt)

                    visit[nxt] = visit[cur] + 1

            if idx >= 3 :

                s = list(cur)

                s[idx], s[idx-3] = s[idx-3], s[idx]

                nxt = ''.join(s)

                if nxt not in visit:

                    queue.append(nxt)

                    visit[nxt] = visit[cur] + 1

            if idx < 3 != 0:

                s = list(cur)

                s[idx], s[idx+3] = s[idx+3], s[idx]

                nxt = ''.join(s)

                if nxt not in visit:

                    queue.append(nxt)

                    visit[nxt] = visit[cur] + 1

        goal = ''.join([str(x) for x in (board[0] + board[1])])

        return visit[goal] if goal in visit else -1

생각해보니 얘도 BFS 문제였다. 그냥 현재 상태를 어떻게 관리하느냐만 구현하면..