[백준 node.js] 7576번_토마토

🚩 7576번_토마토 골드5

 

📖 문제 설명 : N x M 상자 크기에 토마토가 있을 경우, 하루가 지날 때마다 인접 토마토들을 익게 한다.

모든 토마토가 익는 데까지 걸리는 최소 일수 구하기

 

💡 시간 초과를 벗어나기 위해서는 queue 알고리즘을 구현해서 사용 or index가 증가하는 cursor를 두고, queue.length < queueCursor를 사용

 

queue 알고리즘을 구현 예시

const fs = require('fs')
const [mn, ...input] = fs
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n')
const [m, n] = mn.split(' ').map(Number)
const graph = input.map((x) => x.split(' ').map(Number))

// JS에서 BFS 구현시 shift, push로 queue 구현
// shift 연산은 O(n)을 가지므로 시간 초과날 가능성이 높다.
// 따라서 직접 구현해서 시용

//  각각의 노드, 노드의 data와 다음 노드를 가리키고 있다.
class Node {
  constructor(data) {
    this.data = data
    this.next = null
  }
}

// 큐 클래스
class Queue {
  constructor() {
    this.head = null // 제일 앞 노드
    this.rear = null // 제일 뒤 노드
    this.length = 0 // 노드의 길이
  }

  enqueue(data) {
    // 노드 추가.
    const node = new Node(data) // data를 가진 node를 만들어준다.
    if (!this.head) {
      // 헤드가 없을 경우 head를 해당 노드로
      this.head = node
    } else {
      this.rear.next = node // 아닐 경우 마지막의 다음 노드로
    }
    this.rear = node // 마지막을 해당 노드로 한다.
    this.length++
  }

  dequeue() {
    // 노드 삭제.
    if (!this.head) {
      // 헤드가 없으면 한 개도 없는 것이므로 false를 반환.
      return false
    }
    const data = this.head.data // head를 head의 다음 것으로 바꿔주고 뺀 data를 return
    this.head = this.head.next
    this.length--

    return data
  }
}

// 인덱스 검증
function isRange(dx, dy) {
  if (dx >= 0 && dy >= 0 && dx < n && dy < m) {
    return true
  }
  return false
}

function BFS(graph, queue) {
  // 상하좌우
  const dx = [-1, 1, 0, 0]
  const dy = [0, 0, -1, 1]
  let day = 0

  while (queue.length) {
    let [i, j, cnt] = queue.dequeue()
    for (let k = 0; k < 4; k++) {
      let mx = i + dx[k]
      let my = j + dy[k]
      if (isRange(mx, my) && graph[mx][my] === 0) {
        graph[mx][my] = 1
        queue.enqueue([mx, my, cnt + 1])
      }
    }
    day = cnt
  }
  let answer = day

  // BFS 수행 후 0이 있을 경우 토마토가 익지 못하는 상황 발생
  graph.forEach((_, i) => {
    if (graph[i].includes(0)) {
      answer = -1
    }
  })

  return answer
}

function solution() {
  let answer = 0
  const queue = new Queue()
  graph.forEach((_, i) => {
    graph[i].forEach((_, j) => {
      if (graph[i][j] === 1) {
        queue.enqueue([i, j, 0])
      }
    })
  })

  // BFS 함수 수행하고 나면 인접 토마토가 모두 익게 된다.
  answer = BFS(graph, queue)

  return answer
}
console.log(solution())

 

index를 이용하여 해결한 예시 (이 외의 코드는 동일)

....
....
function BFS(graph, queue) {
  // 상하좌우
  const dx = [-1, 1, 0, 0]
  const dy = [0, 0, -1, 1]
  let day = 0
  let index = 0

  while (queue.length > index) { // index 이용
    let [i, j, cnt] = queue[index++]
    for (let k = 0; k < 4; k++) {
      let mx = i + dx[k]
      let my = j + dy[k]
      if (isRange(mx, my) && graph[mx][my] === 0) {
        graph[mx][my] = 1
        queue.push([mx, my, cnt + 1])
      }
    }
....
....

 

👨‍💻 코드 설명

상자 (graph)를 돌면서 토마토의 위치 정보를 전부 queue에 저장해 준다.

queue를 가지고 흔한 BFS 알고리즘을 사용해 주면 된다. 그러면 최소한의 일수를 구할 수 있다.

 

사실 이 문제는 이전에 해결하지 못했었다. 예전에는 다른 블로그들을 참고해도 동일하게 queue를 사용해서 했는데 그대로 로직을 구성했지만, 시간 초과가 계속 났었다. 그래서 단순 언어적의 한 계로 풀지 않고 미뤄뒀었다.

이번에 다시 풀게 되면서 시간 초과를 해결하기 위해 queue를 구현하였고(오픈 소스), 또 다른 풀이를 통해 index로 해결하는 법을 알 수 있었다.

 

잘못된 설명, 코드, 예외 케이스가 있다면 댓글 남겨주시면 수정하겠습니다.