Baekjoon 1525. 퍼즐 / Python

• 현재의 문자열을 딕셔너리에 저장한다 : {문자열 : 이동횟수}
• 이동횟수가 적은 순으로 bfs
• 문자열이 123456780이 되는 경우 종료

from collections import deque

# 초기 상태
question = ''
for _ in range(3):
    question += ''.join(input().split())

# 목표 상태
goal = '123456780'

# 상태 거리 저장 딕셔너리와 BFS 큐 초기화
dic = {question: 0}
q = deque([question])

# BFS 탐색
while q:
    now = q.popleft()
    
    # 목표 상태에 도달한 경우
    if now == goal:
        print(dic[now])
        exit(0)
    
    # '0'의 현재 위치 찾기
    zero = now.find('0')
    
    # 이동 가능한 방향 정의 (우, 하, 좌, 상)
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    # 각 방향으로 이동 시도
    for dx, dy in directions:
        nx, ny = zero // 3 + dx, zero % 3 + dy
        if 0 <= nx < 3 and 0 <= ny < 3:  # 범위 체크
            next_pos = 3 * nx + ny
            # 상태 변경
            tmp = list(now)
            tmp[zero], tmp[next_pos] = tmp[next_pos], tmp[zero]
            next_state = ''.join(tmp)
            
            # 새로운 상태를 큐에 추가
            if next_state not in dic:
                dic[next_state] = dic[now] + 1
                q.append(next_state)

# 목표 상태에 도달하지 못한 경우
print(-1)