과정
1. 3x3리스트를 문자열로, 문자열을 리스트로 바꿔주는 함수를 만듬
2. 처음 0의 좌표를 저장
3. deque와 defaultdict를 이용해서 각 문자열을 만들 수 있는 최소 횟수를 저장
4. que에 문자열과 0의좌표를 넣고 반복문
- 일반 bfs와 같이 탐색 -> temp_str에 오리지널을 deepcopy
- dic[temp_str] == 0 이면 아직 방문안한 문자열이기 때문에 que에 추가
- 마지막 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
