[boj] 7576. 토마토 (node.js)

문제 요약

[boj] 7576. 토마토 (node.js)

풀이

• 분명 올바르게 코드를 짠 것 같은데 시간초과로 넘어가질 않아, Queue 를 클래스로 구현하니 시간 내에 올바르게 풀이할 수 있었다.
• 전형적인 bfs 문제로, 탐색해야 하는 모든 영역을 탐색했다면 최소 거리를 출력하고, 탐색할 수 없는 영역이 존재한다면 -1을 출력하면 된다.

내 풀이

const readline = require("readline")
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
})

class Node {
  constructor(data = null, next) {
    this.value = data
    this.next = null
  }
}

class Queue {
  constructor(data) {
    this.first = null
    this.last = null
    this.size = 0
  }

  enqueue(val) {
    let node = new Node(val)
    if (!this.first) {
      this.first = node
      this.last = node
    } else {
      this.last.next = node
      this.last = node
    }
    return ++this.size
  }

  dequeue() {
    if (!this.first) return null
    let node = this.first
    if (this.first == this.last) this.last = null
    this.first = this.first.next
    this.size--
    return node.value
  }
}

const dir = [
  [-1, 0],
  [0, 1],
  [1, 0],
  [0, -1],
]

const solution = () => {
  let [m, n] = input().split(" ").map(Number)
  let arr = []
  let dist = []
  let queue = new Queue()
  let visited = []
  let tomato = m * n
  for (let i = 0; i < n; i++) {
    arr[i] = input().split(" ").map(Number)
    visited[i] = []
    dist[i] = []
    arr[i].forEach((elem, col) => {
      if (elem == 0) return
      else if (elem == -1) tomato--
      else {
        queue.enqueue([i, col])
        visited[i][col] = 1
        dist[i][col] = 0
        tomato--
      }
    })
  }

  let max = 0
  if (tomato) bfs()
  else console.log(0)

  function bfs() {
    while (queue.size > 0) {
      let [row, col] = queue.dequeue()
      for (let i = 0; i < 4; i++) {
        let nrow = row + dir[i][0]
        let ncol = col + dir[i][1]
        if (nrow < 0 || nrow >= n || ncol < 0 || ncol >= m) continue
        if (arr[nrow][ncol] == -1) continue
        if (visited[nrow][ncol]) continue
        if (arr[nrow][ncol] == 0) tomato--
        visited[nrow][ncol] = 1
        dist[nrow][ncol] = dist[row][col] + 1
        max = dist[nrow][ncol]
        queue.enqueue([nrow, ncol])
      }
    }
    tomato == 0 ? console.log(max) : console.log(-1)
  }
}

let _line = 0
const input = () => stdin[_line++]

let stdin = []
rl.on("line", function (line) {
  stdin.push(line)
}).on("close", function () {
  solution()
  process.exit()
})

주절주절

• 벌써 4월이다! 시간이 너무 빠르게 지나간다. 자바스크립트로 풀이할 때마다 아, C++로 할 걸, 아, 파이썬으로 할 걸... 요런 생각을 자주 했었는데, 지금 생각해보면 언어를 손에 익히고 리액트 연습을 하고, 데이터를 처리하는 데 이 불편한 백준 문제 풀이가 큰 도움이 된 것 같다. 뿌듯하다! ^_^*
• 알고리즘 문제를 풀이하는 속도가 빨라진 만큼 집중해서 더 많이 풀이할 수 있도록 시간 활용을 잘 해보자.