[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++로 할 걸, 아, 파이썬으로 할 걸... 요런 생각을 자주 했었는데, 지금 생각해보면 언어를 손에 익히고 리액트 연습을 하고, 데이터를 처리하는 데 이 불편한 백준 문제 풀이가 큰 도움이 된 것 같다. 뿌듯하다! ^_^*
- 알고리즘 문제를 풀이하는 속도가 빨라진 만큼 집중해서 더 많이 풀이할 수 있도록 시간 활용을 잘 해보자.
Author And Source
이 문제에 관하여([boj] 7576. 토마토 (node.js)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@greenish0902/boj-7576.-토마토-node.js저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)