백준알고리즘 - 1525번 퍼즐 - 파이썬(Python)

문제

3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다.

1	2	3
4	5	6
7	8

어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 다음의 예를 보자.

1		3
4	2	5
7	8	6

1	2	3
4		5
7	8	6

1	2	3
4	5
7	8	6

1	2	3
4	5	6
7	8

가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.

 

입력

 

세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.

 

출력

첫째 줄에 최소의 이동 횟수를 출력한다. 이동이 불가능한 경우 -1을 출력한다.

 

예제 입력과 출력

 

 

정답

 

from collections import deque
import sys
input= lambda : sys.stdin.readline().strip()

def bfs():
    de=deque()
    de.append(aa)
    dist[aa] = 0
    
    while de:
        d = de.popleft()
        if d == 123456789:
            return dist[d]
        
        s = str(d)
        k = s.find('9')
        x, y = k//3, k%3 # 3X3표일 때 x,y 좌표
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < 3 and 0 <= ny < 3:
                nk = nx*3 + ny # 3x3 표에서 x,y 좌표를 리스트로 바꿨을때의 위치
                ns = list(s)
                ns[k], ns[nk] = ns[nk], ns[k]
                nd = int(''.join(ns))
                
                if not dist.get(nd): 
                    dist[nd] = dist[d]+1
                    de.append(nd)
                    
    return -1

dx=[1,-1,0,0]
dy=[0,0,1,-1]

dist = dict()
aa=''

for i in range(3):
    a=input()
    a=a.replace(' ','')
    aa += a

aa=int(aa.replace('0','9'))

print(bfs())

1. 3x3 표를 하나의 문자열로 생각합니다. 이때 0은 9로 바꿉니다.
2. 딕셔너리를 통해 키는 퍼즐 형태, 값은 퍼즐 이동 수로 표현합니다.

3. bfs를 통해 문자열에서 9의 위치를 기준으로 위, 아래, 왼쪽, 오른쪽으로 옮깁니다.
4. 옮기면서 이동 수를 하나씩 늘리고 문자열이 123456789가 나오면 이동 수를 출력하고 큐에 남은 값이 없을 때까지 123456789가 나오지 않으면 -1을 출력합니다.

 

---

백준 알고리즘 1525번 : https://www.acmicpc.net/problem/1525

1525번: 퍼즐