[JavaScript/BFS] 백준 골드 5 : 7576 - 토마토

https://www.acmicpc.net/problem/7576

7576번: 토마토

---

📌 작성한 코드 

// 7576

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

const [M, N] = input.shift().split(" ").map(Number);
let remains = 0;
const tomatoes = [];

for (let i = 0; i < N; i++) {
    const temp = input.shift().split(" ").map(Number);
    tomatoes.push(temp);
    remains += temp.filter((item) => item === 0).length;
}

const startTomatoes = [];
for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
        if (tomatoes[i][j] === 1) {
            startTomatoes.push([i, j, 1]);
        }
    }
}

const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];

const solution = () => {
    const bfs = () => {
        const queue = [...startTomatoes];

        let idx = 0;
        while (queue.length > idx) {
            const [x, y, d] = queue[idx++];
            tomatoes[x][y] = d;

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

                if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                if (tomatoes[nx][ny] === 0) {
                    tomatoes[nx][ny] = d + 1;
                    queue.push([nx, ny, d + 1]);
                    remains--;
                }
            }

            if (remains <= 0) return queue[queue.length - 1][2];
        }
        return queue[queue.length - 1][2];
    };

    if (startTomatoes.length === 0) return console.log(-1);
    const answer = bfs() - 1;
    remains > 0 ? console.log(-1) : console.log(answer);
};

solution();

 

---

📌 풀이 

풀이는 이전에 푼 토마토(더 어려운 버전) 참고하기! 거의 똑같은 문제이고 H에 대한 부분만 제외하고 풀면 지금 문제와 똑같다.

https://youme016.tistory.com/226

[JavaScript/BFS] 백준 골드 5 : 7569 - 토마토

 

알고리즘 공부를 다시 시작하면서 풀어본 문제였는데 어렵지 않게 풀 수 있었다. 그러나 런타임 에러(TypeError)가 발생해서 해결하는데 애를 먹었다. 해당 문제에서 런타임 에러가 발생한 이유는 익은 토마토가 하나도 없는 경우에는 bfs에서 queue가 비어있게 되는데 return값으로 queue에 접근하려고 해서 문제가 발생하는 것이다. 그래서 bfs 작동시키기 전에 미리 확인하고, 익은 토마토가 하나도 없다면 바로 -1을 출력할 수 있게 다음 코드를 추가해주었다. 

if (startTomatoes.length === 0) return console.log(-1);

 

---

✅ 성공