[백준 1035번] 조각 움직이기 (Python3)

import collections,itertools,copy
dy = [1,-1,0,0]
dx = [0,0,1,-1]

def BFS(n,board):
  y,x = piece[n]
  board[y][x] = 0
  dq = collections.deque([(y,x,0)])
  visited = [[0]*5 for i in range(5)]
  arr = []
  distance = 25
  while dq:
    y,x,d = dq.popleft()
    if visited[y][x] or d>distance:
      continue
    visited[y][x] = 1
    for i in range(4):
      y1,x1 = y+dy[i],x+dx[i]
      if 5>y1>=0 and 5>x1>=0:
        if board[y1][x1]==P[0] and not board[y][x]:
          distance = d
          arr.append((y,x))
        else:
          dq.append((y1,x1,d+1))
  return distance,arr

def DFS(i,distance,board):
  global result
  if i==N:
    result = min(result,distance)
    return
  newboard = copy.deepcopy(board)
  d,arr = BFS(P[i],newboard)
  for y,x in arr:
    newboard[y][x] = P[0]
    DFS(i+1,distance+d,newboard)
    newboard[y][x] = 0    

board = [[*map(lambda x:1 if x=="*" else 0,input().strip())] for i in range(5)]

piece,N = {},0
for y in range(5):
  for x in range(5):
    if board[y][x]:
      N += 1
      board[y][x] = N
      piece[N] = y,x

result = 100
for P in itertools.permutations(range(1,N+1),N):
  DFS(1,0,board)
  y,x = piece[P[0]]
  board[y][x] = 0
  for i in range(4):
    y1,x1 = y+dy[i],x+dx[i]
    if 5>y1>=0 and 5>x1>=0:
      board[y1][x1] = P[0]
      DFS(1,1,board)
      board[y1][x1] = 0
  board[y][x] = P[0]
print(result)

꽤나 까다로운 문제였다.

내가 푼 방식부터 설명하면,

1. 조각의 개수를 구한 뒤, 조각에 번호를 붙이고 permutations 함수를 이용해 모든 순열을 구한다.

2. 순열 순서대로 처음 조각은 고정시킨 뒤, 다음 조각들을 차례차례 붙인다.

3. 최솟값을 구한다.

 

이렇게 해결하려고 코드를 짰다.

그러나 반례가 존재했으니, 2번에서 처음 조각을 고정시키는 것이 잘못된 풀이였다. 모든 조각을 다 움직여야 하는 경우가 존재했던 것이다. 예를 들면,

의 경우 사진처럼 5가 정답이지만, 내 방식처럼 처음 조각을 고정시킬 경우 최솟값이 6이 나오게 된다.

그래서 어떻게 해결할까 고민하다가 그냥 처음 조각을 1씩만 움직이기로 했다. 어차피 보드의 크기가 매우 작기 때문에 처음 조각을 2 이상 움직여야 최솟값이 나오는 경우는 존재하지 않기 때문이다.

 

 

오늘의 교훈) 다양한 반례를 염두하자