[백준 4991번] 로봇 청소기 (Python3)

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

def BFS(y,x,n):
  visited = [[0]*M for i in range(N)]
  dq = deque()
  dq.append((y,x,0))

  while dq:
    y,x,d = dq.popleft()
    if visited[y][x]:
      continue
    visited[y][x] = 1
    if room[y][x] == "*":
      n1 = numdict[(y,x)]
      graph[n][n1] = graph[n1][n] = d
    for i in range(4):
      y1,x1 = y+dy[i],x+dx[i]
      if N>y1>=0 and M>x1>=0:
        if room[y1][x1] == "x" or visited[y1][x1]:
          continue
        dq.append((y1,x1,d+1))    

def DFS(now,distance,cnt):
  global result
  if distance >= result:
    return
  if cnt == num:
    result = min(result,distance)
    return
  for next in range(1,num+1):
    if visited[next]:
      continue
    visited[next] = 1
    DFS(next,distance+graph[now][next],cnt+1)
    visited[next] = 0

while True:
  M,N = map(int,input().split())
  if not N:
    break
  room = []
  for i in range(N):
    room.append([*input().strip()])

  numdict = {}
  dirty = {}
  num = 0
  for y in range(N):
    for x in range(M):
      if room[y][x] == "o":
        robot = (y,x)
      elif room[y][x] == "*":
        num += 1
        numdict[(y,x)] = num
        dirty[num] = (y,x)

  result = INF
  graph = [[INF]*(num+1) for i in range(num+1)]
  BFS(*robot,0)
  
  for i in range(1,num+1):
    if graph[0][i] == INF:
      result = -1
      break
  if result == -1:
    print(-1)
    continue

  for i in range(1,num):
    BFS(*dirty[i],i)

  visited = [0]*(num+1)
  DFS(0,0,0)
  print(result)

처음에 문제를 읽어보고 "엥? 이거 외판원 순회 아니야? 이거를 어떻게 풀지??" 라고 생각했다.

 

그런데 찬찬히 읽어보니까 더러운 칸의 개수가 10개밖에 안된다는 말이 쓰여있었다. 어쩐지

10개 이하의 외판원 순회는 브루트 포스로도 충분히 풀 수 있기 때문에 브루트 포스로 해결하였다. 

 

알고리즘은

1. BFS로 로봇청소기에서 모든 더러운 칸까지의 거리를 조사한다

2. 1에서 조사할 수 없는 칸이 있다면 -1 출력

3. 모든 더러운 칸에서 다른 모든 더러운 칸까지의 거리를 조사한다.

4. 1,3에서 얻은 그래프 데이터로 DFS를 하여 브루트 포스로 최소비용을 구한다.

 

만약 더러운 칸의 개수가 16개가 된다면 아마 비트마스킹을 이용한 DP로 풀어야할 것이다.

 

오늘의 교훈) 문제를 끝까지 잘 읽어보자