[백준 1525번] 퍼즐(파이썬)

https://www.acmicpc.net/problem/1525

1525번: 퍼즐

이 문제는 좌표평면에 대해서

다르게 관점을 가지게 해준 좋은 문제입니다.

 

우선, 이 문제는

백트레킹을 공부하셨더라면

'백트레킹쓰면서

퍼즐 좌표를 다 받아야하는건가?'

라는 생각이 자연스럽게 듭니다.

물론 이 방식이 틀린 방법은 아니지만

메모리를 확~~넘게 됩니다.

 

그럼 어떻게 숫자를 저장하지??

구글링해본 결과

퍼즈를 숫자로 바꾸면서

구할 수 있었습니다.

파이썬은 딕셔너리에 숫자를 저장해주어서

dict[숫자]=걸리는 시간

이렇게 저장해주면

문제를 풀어낼 수 있었습니다.

#백준 1525번 퍼즐
from collections import deque
from copy import deepcopy
fin=123456789
puzzle=[]
q=deque()
dx=[1,-1,0,0]
dy=[0,0,1,-1]
num=0
for i in range(3):
    tmp=list(map(int,input().split()))
    for j in range(3):
        if tmp[j]==0:
            tmp[j]=9
        num=num*10+tmp[j]
    puzzle.append(tmp)
answer=1e9
dp=dict()
dp[num]=0


q.append(num)

while q:
    now=q.popleft()


    if now==fin:
        answer=min(answer,dp[fin])

        break
    nu=str(now)
    nu=list(nu)

    x = nu.index('9') // 3
    y = nu.index('9') % 3

    for d in range(4):
        nx=x+dx[d]
        ny=y+dy[d]

        if nx<0 or nx>=3 or ny<0 or ny>=3:
            continue

        new_num=deepcopy(nu)
        new_num[x*3+y],new_num[nx*3+ny]=new_num[nx*3+ny],new_num[x*3+y]
        new_num="".join(new_num)
        new_num=int(new_num)

        if not dp.get(new_num):
            dp[new_num]=dp[now]+1
            q.append(new_num)



if answer==1e9:
    answer=-1

print(answer)

좌표평면의 좌표를 다르게 해석하면서

이전의 자료들을 어떻게 받아낼지

다른 관점으로 생각하게 만든 좋은 문제입니다.

발상자체가 특이해서 정리해봄직하네요.