[백준/1525] 퍼즐 (Python)

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

1525번: 퍼즐

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:17:57

 

---

 

문제 설명

 

 

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

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

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

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

1 0 3
4 2 5
7 8 6

 

출력 예시

 

3

 

 

---

 

풀이

 

언뜻 보기엔 약 9! = 362880 의 경우의 수를 전부 테스트해봐야할 수도 있다고 생각할 수 있다. 하지만 실제 경우의 수는 그렇게 많지 않다.

 

슬라이드 퍼즐 알고리즘 (Slide Puzzle Algorithm)

 

이 링크에도 잘 설명되어있으니 참고하면 좋다(풀이 이후에 발견했는데, 이런게 있었구나..싶다)

 

즉 비교적 소수의 경우의 수이므로, 완전탐색이 가능해보인다. BFS로 풀이하여 최댓값을 바로 발견할 수 있을 것이다. 현재 0 위치에서 이동 가능한 상하좌우 퍼즐을 확인하고, 만약 이동 가능하다면 그 위치의 다른 퍼즐과 교환한다. 방문한 적이 없다면 그 방향으로 탐색을 진행한다. 방문 여부는 집합 자료구조를 통해서 매우 쉽게 구현 가능하다.

 

 

풀이 코드

from collections import deque

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

for i in range(3) :
  num = input().strip().replace(" ","")
  for j in range(3) :
    if num[j] == '0' :
      x, y = j, i
  nums += num

q = deque([(0, x, y, nums)])
visited = { nums }

while q :
  move, x, y, nums = q.popleft()
  if nums == '123456780' :
    print(move)
    exit()
  nums = list(nums)
  for k in range(4) :
    ax, ay = x + dx[k], y + dy[k]
    if -1 < ax < 3 and -1 < ay < 3 :
      nums[x + y*3], nums[ax + ay*3] = nums[ax + ay*3], nums[x + y*3]
      tmp = ''.join(nums)
      if tmp not in visited :
        visited.add(tmp)
        q.append((move+1, ax, ay, tmp))
      nums[x + y*3], nums[ax + ay*3] = nums[ax + ay*3], nums[x + y*3]
      
print(-1)

풀이 완료!