[python] 백준 1525 퍼즐

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

1525번: 퍼즐

 

 

문제 해결

 표에 숫자를 넣고 빈 곳(0)을 이용해 이동하는 문제

 이동 방법은 동서남북이므로 move =[(-1,0), (1,0), (0,-1), (0,1)] 4가지가 있다.

 위의 조건과 최소 이동 번수를 구하는 것이므로 아무래도 bfs가 좋다.

 그런데 어떻게 풀어야하지?? (ㅜㅜ)

 

답은 리스트가 아니라 문자열 이용!

1	2	3
4	5	6
7	8	9

위 표는 "123456789" 문자열로 변환 시킬 수 있다!

그리고 n 위치는 (n//3, n%3) 으로 좌표를 만들 수 있다.

그러면 이동 하는 bfs 함수 만들고 끝!

 

 

CODE

from collections import deque
import sys

move = [(-1,0), (1,0), (0,-1), (0,1)]
dist = dict() # 각 문자열이 걸리는 최소 시간(횟수)를 나타내는 딕셔너리
start = ""
for i in range(3):
    a = str(input()).strip()
    a.replace(" ","")
    start += a
start.replace('0','9') #문자열을 쓸때 0이 9자리에 와야하므로 9로 바꿔주는 것이 편하다.
dist[start] = 0

def bfs():
    que = deque()
    que.append(start)
    while que:
        x = que.popleft()
        if x=="123456789": # 정답이 나오면
            return dist[x]
        s = str(x)
        k = s.find('9')
        a, b = k//3, k%3
        for i in range(4):
            na = a + move[i]
            nb = b + move[i]
            if 0<=na<3 and 0<=nb<3:
                nk = na*3 + nb
                ns = list(s)
                ns[k], ns[nk] = ns[nk], ns[k]
                nx = int(''.join(ns))
                if not dist.get(nx):
                    dist[nx] = dist[x] + 1
                    que.append(nx)
    return -1
print(bfs())