[javascript] 백준 7576번 토마토

문제보기

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

const [N, M] = input
    .shift()
    .split(" ")
    .map((value) => +value);
const box = input.map((item) => item.split(" ").map((value) => +value));
const visited = new Array(M).fill(0).map(() => new Array(N).fill(0));

const direction = [
    [-1, 0],
    [0, -1],
    [1, 0],
    [0, 1],
];
let result = 0;
let ripe = 0;
let unripe = 0;
const BFS = (start) => {
    let queue = [...start];
    let q = 0;
    while (queue.length > q) {
        let [x, y] = queue[q];
        q++;
        if (box[x][y]) {
            for (let i = 0; i < 4; i++) {
                let [dx, dy] = [x + direction[i][0], y + direction[i][1]];
                if ((dx < 0) | (dy < 0) | (dx >= M) | (dy >= N)) continue;
                if (box[dx][dy] === -1 || box[dx][dy] >= 1) continue;
                visited[dx][dy] = visited[x][y] + 1;
                box[dx][dy] = 1;
                ripe += 1;
                unripe -= 1;
                result =
                    visited[x][y] + 1 > result ? visited[x][y] + 1 : result;
                queue.push([dx, dy]);
            }
        }
    }
};
let ripeLocation = [];
for (let x = 0; x < M; x++) {
    for (let y = 0; y < N; y++) {
        if (box[x][y] === 1) {
            ripeLocation.push([x, y]);
            ripe += 1;
        }
        if (box[x][y] === 0) {
            unripe += 1;
        }
    }
}
BFS(ripeLocation);

if (unripe) {
    console.log(-1);
} else {
    console.log(result);
}

풀이
BFS로 풀이했다
맨처음에 익은 토마토가 있는 좌표를 구해서 BFS에 한번에 전달했다
하루가 지날때마다 상하좌우로 익지 않은 토마토가 있다면 익은 토마토가 생기게 구현했고
익은 토마토와 안익은 토마토의 갯수를 체크해주었다.

BFS의 실행이 끝나고나서 안익은 토마토가 있다면 -1을 출력하고 그 외에는 최소 일수를 출력하게 구현했다.

BFS는 기본적으로 queue를 이용한 선입선출으로 구현이되나 shift 메소드를 사용시 시간초과가 발생해서 while문 조건에 변형을 줘서 실행시마다 인덱스가 1씩 증가하게 해놓았다.