[백준 #1525]: 퍼즐 (python)

백준#1525: 퍼즐

import sys
from collections import deque
input = sys.stdin.readline


def bfs(puzzle):
    queue=deque([puzzle])
    visited[puzzle]=0
    while queue:
        puzzle=queue.popleft()
        if puzzle == "123456780":
            return visited["123456780"]
        pos = puzzle.index('0') 
        row=pos//3
        col=pos%3
        for x,y in move:
            move_row=row + x
            move_col=col + y
            if 0 <= move_row < 3 and 0 <= move_col < 3:
                move_pos=move_row*3+move_col
                temp_puzzle=list(puzzle)
                temp_puzzle[pos],temp_puzzle[move_pos] = temp_puzzle[move_pos],temp_puzzle[pos]
                temp_puzzle = "".join(temp_puzzle)
                if temp_puzzle not in visited:
                    queue.append((temp_puzzle))
                    visited[temp_puzzle]=visited[puzzle]+1

    return -1


visited={}
row=0
col=0
move=[[-1,0],[1,0],[0,-1],[0,1]]
count=0
puzzle = ""
for _ in range(3):
    temp = input().strip()
    temp = temp.replace(" ", "")
    puzzle += temp

print(bfs(puzzle))

해당 문제는 기본적인 bfs문제이다. 하지만 중요한점은 2차원 배열으로 처리할 경우 시간이 오래 걸린다. 그래서 문자열로 처리해야한다.