[JS] 백준 4991 로봇 청소기

백준 4991 로봇 청소기

풀이

처음에는 간단하게 청소기에서부터 BFS를 시작하고 가까운 더러운 방을 마주하고 그 방부터 다시 BFS를 돌리는, 무조건 가장 짧은 거리의 방을 선택하여 이동하는 그리디적인 생각으로 풀이를 하였습니다. 하지만 역시 골1은 그렇게 간단하게 풀릴리가 없었습니다.
위의 풀이는 문제에 주어진 예제는 모두 맞았지만 반례가 있습니다.

5 5
....*
.*.*.
..o..
..*..
.....

이러한 예제가 주어졌을 때, 위의 풀이는 dx, dy의 구성에 따라 다르지만 10을 출력할 때가 있습니다. 하지만 이 입력의 정답은 8입니다. 이 경우, 2행에 있는 더러운 방 2개 중 어디를 먼저 방문하냐에 따라 10이 되기도 하고 8이 되기도 합니다. 또한

5 5
....*
*..*.
..o..
..*..
.....

이러한 예제에서는 4행에 있는 더러운 방에서 가장 가까운 방이 아닌 그 다음 방으로 이동해야 최소 이동 거리를 출력할 수 있습니다.
따라서 처음 생각한 풀이는 틀렸습니다.

그리고 생각한 풀이는 BFS를 재귀적으로 돌리는 것입니다.
더러운 방에 도착했을 때 모든 방을 청소할 수 있는 경우의 수를 다 탐색하는 것입니다.

코드

const fs = require('fs')
const filePath = process.platform === 'linux' ? 'dev/stdin' : './input.txt'
let input = fs.readFileSync(filePath).toString().trim().split('\n')

input.reverse()

let result = Infinity,
  dx = [1, -1, 0, 0],
  dy = [0, 0, 1, -1]
let w, h
let room = []

while (true) {
  result = Infinity
  const size = input.pop().split(' ').map(Number)
  w = size[0]
  h = size[1]

  if (w === 0 && h === 0) break

  room = Array(h)
  for (let i = 0; i < h; i++) {
    room[i] = input.pop().trim().split('')
  }

  // 더러운 방 갯수 세고 청소기 위치 찾기
  let dirty = 0,
    robotX = -1,
    robotY = -1

  for (let i = 0; i < h; i++) {
    for (let j = 0; j < w; j++) {
      if (room[i][j] === '*') dirty += 1
      else if (room[i][j] === 'o') {
        robotX = i
        robotY = j
      }
    }
  }

  // 청소기에서부터 bfs 돌기
  bfs(robotX, robotY, 0, dirty)

  if (result === Infinity) console.log(-1)
  else console.log(result)
}

function bfs(x, y, depth, dirty) {
  if (depth > result) return
  if (dirty === 0) {
    result = Math.min(result, depth)
    return
  }
  let visited = Array.from(Array(h), () => Array(x).fill(false))
  let queue = []
  queue.push({ x, y, depth, dirty })
  visited[x][y] = true

  while (queue.length > 0) {
    const temp = queue.shift()

    if (temp.depth > result) break

    if (room[temp.x][temp.y] === '*') {
      room[temp.x][temp.y] = '.'
      bfs(temp.x, temp.y, temp.depth, temp.dirty - 1)
      room[temp.x][temp.y] = '*'
      continue
    }

    for (let i = 0; i < 4; i++) {
      const nx = temp.x + dx[i]
      const ny = temp.y + dy[i]

      if (nx < 0 || ny < 0 || nx >= h || ny >= w || visited[nx][ny] || room[nx][ny] === 'x')
        continue

      visited[nx][ny] = true
      queue.push({ x: nx, y: ny, depth: temp.depth + 1, dirty: temp.dirty })
    }
  }
}

이 풀이는 시간 초과를 조심해야 합니다. 무작정 모든 경우의 수를 다 탐색한다면 시간 초과가 발생합니다. 따라서 현재 result보다 이미 이동 횟수를 초과했다면 탐색을 중단하는 처리를 해주어야 합니다.