problem-1525

과정
1. 3x3리스트를 문자열로, 문자열을 리스트로 바꿔주는 함수를 만듬
2. 처음 0의 좌표를 저장
3. deque와 defaultdict를 이용해서 각 문자열을 만들 수 있는 최소 횟수를 저장
4. que에 문자열과 0의좌표를 넣고 반복문

1. 일반 bfs와 같이 탐색 -> temp_str에 오리지널을 deepcopy
2. dic[temp_str] == 0 이면 아직 방문안한 문자열이기 때문에 que에 추가
3. 마지막 dic[target]에서 1을 뺀 후 출력, defaultdict(int)의 기본값은 0이기 때문에 초기값을 1로 저장해서 마지막에 빼줘야함.

from collections import defaultdict
from collections import deque
import copy
def board_to_str(board):
    result=''
    for i in board:
        result+=''.join(i)
    return result

def str_to_board(str):
    result=[[],[],[]]
    for i in range(9):
        result[i//3].append(str[i])
    return result

board=[]
zero_x,zero_y=0,0
for i in range(3):
    
    board.append(list(input().split()))
    for j in range(3):
        if board[i][j]=='0':
            zero_x,zero_y=i,j
    
b_str =board_to_str(board)

que=deque([(b_str,zero_x,zero_y)])
target = '123456780'
dic = defaultdict(int)
dic[b_str]=1
dx=[1,0,-1,0]
dy=[0,1,0,-1]


while que:
    b,x,y = que.popleft()
    if b==target:
        break
    board_b = str_to_board(b)

    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if nx>=0 and ny>=0 and nx<3 and ny<3:
            temp_board = copy.deepcopy(board_b)
            temp_board[nx][ny],temp_board[x][y] = temp_board[x][y],temp_board[nx][ny]
            temp_str = board_to_str(temp_board)
            if dic[temp_str]==0:
                dic[temp_str]=dic[b]+1
                que.append((temp_str,nx,ny))
print(dic[target]-1)

time:40분
resolve:X