[백준 1525번] 퍼즐 (Python3)

import sys
input = sys.stdin.readline
from collections import deque
dy = [1,-1,0,0]
dx = [0,0,1,-1]

puzzle = ""
for i in range(3):
  puzzle += "".join(input().split())

memory = set()

result = -1
dq = deque()
dq.append((puzzle,0))
while dq:
  p,cnt = dq.popleft()
  if p in memory:
    continue
  if p == "123456780":
    result = cnt
    break
  memory.add(p)
  zero = p.find("0")
  y,x = zero//3,zero%3
  plist = [[*p[:3]],[*p[3:6]],[*p[6:]]]
  for i in range(4):
    y1,x1 = y+dy[i],x+dx[i]
    if 3>y1>=0 and 3>x1>=0:
      plist[y][x] = plist[y1][x1]
      plist[y1][x1] = "0"
      dq.append((("".join(map(lambda x:"".join(x),plist))),cnt+1))
      plist[y1][x1] = plist[y][x]
      plist[y][x] = "0"

print(result)

BFS + 백트래킹으로 해결하였다.

 

기본적인 알고리즘은,

1. deque에 퍼즐의 숫자를 일렬로 나열한 문자열을 저장한다.

2. memory에 현 문자열이 이미 있으면 continue, 없으면 추가한다.

3. 4방향에 대해서 탐사한다.

4. cnt 출력

 

이때 이 문제를 DFS로 해결하려고 시도하면 틀리게 된다. 왜냐하면 같은 모양을 다른 cnt로 만들 수가 있는데 DFS로 문제를 풀면 더 작은 cnt가 있음에도 불구하고 이미 memory에 해당 문자열이 존재하여 최솟값을 찾을 수 없게 되기 때문이다.

 

 

오늘의 교훈) 문제에 따라 BFS, DFS를 신중히 고민하자