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

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

7569번: 토마토

---

📌 작성한 코드 1 (런타임 에러) 

// 7569번

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, H] = input.shift().split(" ").map(Number);
let tomatoes = [];
for (let i = 0; i < H; i++) {
    let temp = input.slice(i * 3, i * 3 + 3);
    temp = temp.map((item) => item.split(" ").map(Number));
    tomatoes.push(temp);
}

const check = (arr) => {
    for (let i = 0; i < H; i++) {
        for (let j = 0; j < N; j++) {
            for (let k = 0; k < M; k++) {
                if (arr[i][j][k] === 0) return false;
            }
        }
    }
    return true;
};

const solution = () => {
    const dx = [1, -1, 0, 0, 0, 0];
    const dy = [0, 0, 1, -1, 0, 0];
    const dz = [0, 0, 0, 0, 1, -1];

    const bfs = () => {
        let count = 0;
        const queue = [];
        for (let i = 0; i < H; i++) {
            for (let j = 0; j < N; j++) {
                for (let k = 0; k < M; k++) {
                    if (tomatoes[i][j][k] === 1) queue.push([i, j, k]);
                }
            }
        }

        let day = queue.length;
        let temp = 0;

        while (queue.length) {
            temp++;
            const [z, x, y] = queue.shift();
            for (let i = 0; i < 6; i++) {
                const nz = z + dz[i];
                const nx = x + dx[i];
                const ny = y + dy[i];

                if (nx >= 0 && ny >= 0 && nz >= 0 && nx < N && ny < M && nz < H) {
                    if (tomatoes[nz][nx][ny] === 0) {
                        tomatoes[nz][nx][ny] = 1;
                        queue.push([nz, nx, ny]);
                    }
                }
            }
            if (temp === day) {
                count++;
                temp = 0;
                day = queue.length;
            }
            if (check(tomatoes)) break;
        }
        if (check(tomatoes)) return count;
        return -1;
    };

    return bfs();
};

console.log(solution());

- 3차원 배열에 토마토 상자들을 저장하고, 각 토마토의 6방향을 확인해서 근처에 있는 토마토가 익을 수 있도록 함 

- 날짜를 어떻게 세야할까 고민을 하다가 맨 처음 큐에 저장된 토마토의 개수를 다 확인하면 하루가 지나간다는 것을 이용해서

반복될때마다 temp에 숫자를 증가시키고 해당 숫자만큼 반복되면 하루가 지나갔으므로, 다시 temp를 초기화하고 하루가 지났다고 날짜를 증가시켰다 

- 그리고 마지막에 검사해서 모든 토마토가 다 익었다면 정답을 출력했다 

 

-> 결과 : 런타임 에러 

 

---

 

 

📌 해결 과정 (1) 

- 왜 런타임 에러가 나는 것일까 고민하다가, h가 1 이라서 이차원 배열에 저장할 때 bfs가 제대로 작동하지 않는다는 것을 확인하고 

 h가 1일때와, 아닐때로 나누어서 모든 로직을 이차원과 삼차원으로 다시 작성하고 실행하였더니 시간 초과가 발생했다 

 

📌 해결 과정(2) 

- 다시 코드를 살펴보니 3차원 배열을 검사하는 check를 너무 여러번 사용하는데다가, shift()를 사용해서 시간이 초과된다고 판단하였다.

- 여기서 다른 분의 코드를 참고 하였다 

- 참고 ) https://velog.io/@jiyaho/%EB%B0%B1%EC%A4%80-7569-%ED%86%A0%EB%A7%88%ED%86%A0-Node.js-BFS-%ED%92%80%EC%9D%B4

[백준] 7569 토마토 Node.js (BFS 풀이)

 

이 분의 블로그에서 이런 아이디어를 얻을 수 있었다.

- shift() 대신 인덱스를 증가시키면서 큐 확인하기 

- 맨 처음에 익지 않은 토마토의 수를 세서, 모든 반복이 끝난 후에 익지 않은 토마토의 수가 남아있는지 확인하기 

 

또한 스스로 코드를 디버깅하면서 맨처음 input을 통해 tomatoes를 가져오는 로직에 문제가 있음을 발견하였다. 

그래서 모든 방법을 모아서 다시 코드를 작성하였다.

 

---

 

 

📌 작성한 코드 2 (통과) 

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, H] = input.shift().split(" ").map(Number);
let tomatoes = [];
for (let i = 0; i < H; i++) {
    let temp = [];
    for (let j = 0; j < N; j++) {
        temp.push(input[i * N + j].split(" ").map(Number));
    }
    tomatoes.push(temp);
}

const solution = () => {
    const dx = [1, -1, 0, 0, 0, 0];
    const dy = [0, 0, 1, -1, 0, 0];
    const dz = [0, 0, 0, 0, 1, -1];

    const bfs = () => {
        let unripeTomato = 0;
        let answer = 0;
        const queue = [];
        for (let i = 0; i < H; i++) {
            for (let j = 0; j < N; j++) {
                for (let k = 0; k < M; k++) {
                    if (tomatoes[i][j][k] === 1) queue.push([i, j, k, 0]);
                    if (tomatoes[i][j][k] === 0) unripeTomato++;
                }
            }
        }

        let idx = 0;
        while (queue.length > idx) {
            const [z, x, y, days] = queue[idx++];
            for (let i = 0; i < 6; i++) {
                const nz = z + dz[i];
                const nx = x + dx[i];
                const ny = y + dy[i];

                if (nx >= 0 && ny >= 0 && nz >= 0 && nx < N && ny < M && nz < H) {
                    if (tomatoes[nz][nx][ny] === 0) {
                        tomatoes[nz][nx][ny] = 1;
                        queue.push([nz, nx, ny, days + 1]);
                        unripeTomato--;
                    }
                }
            }
            answer = days;
        }
        return unripeTomato ? -1 : answer;
    };

    return bfs();
};

console.log(solution());

 

📍 풀이 

✅ 1. 3차원 배열에 토마토 저장하기 

- 한 줄의 입력을 잘라서 숫자로 만들어서 배열에 삽입하고 (반복하면 2차원 배열됨) '0 0 0 0 0 1' -> [0,0,0,0,0,1]

- 해당 2차원 배열이 완성되면 (길이가 N이 되면) 다시 토마토 배열에 넣어서 3차원 배열로 만든다.

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, H] = input.shift().split(" ").map(Number);
let tomatoes = [];
for (let i = 0; i < H; i++) {
    let temp = [];
    for (let j = 0; j < N; j++) {
        temp.push(input[i * N + j].split(" ").map(Number));
    }
    tomatoes.push(temp);
}

 

✅ 2. bfs 작성하기 

(1) 맨 처음 익은 토마토의 개수 세기 

- 토마토가 익었다면(1이라면) queue에 넣고, 토마토가 익지 않았다면(-1) 익지 않은 토마토의 개수를 세준다 

- 큐에 삽입할때 현재 며칠이 걸렸는지도 같이 저장하기 위해서 마지막에 0을 저장(날짜)해준다.

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

 

(2) 상하좌우앞뒤 확인해서 토마토 익게 하기 

- 인덱스를 사용해서 queue.shift()시 N의 시간이 걸리는 것을 1로 단축한다.

- 상하좌우 앞뒤를 확인해서 해당 인덱스가 토마토 삼차원 배열의 범위를 넘지 않고, 익지 않은 토마토라면(-1) 

-> 해당 토마토를 익게하고, 해당 토마토의 좌표를 큐에 넣어준다 (하루가 지났으니까 날짜에 +1을 해준다) 

-> 그리고 토마토가 익었으니까 익지 않은 토마토의 수를 감소시킨다 

- 반복문 한번 끝날 때마다 현재까지 지나온 날짜(days)를 답에 저장해준다. 

let idx = 0;
        while (queue.length > idx) {
            const [z, x, y, days] = queue[idx++];
            for (let i = 0; i < 6; i++) {
                const nz = z + dz[i];
                const nx = x + dx[i];
                const ny = y + dy[i];

                if (nx >= 0 && ny >= 0 && nz >= 0 && nx < N && ny < M && nz < H) {
                    if (tomatoes[nz][nx][ny] === 0) {
                        tomatoes[nz][nx][ny] = 1;
                        queue.push([nz, nx, ny, days + 1]);
                        unripeTomato--;
                    }
                }
            }
            answer = days;

 

(3) 답 리턴 

- bfs가 끝나고 난 후에, 여전히 익지 않은 토마토가 존재한다면 -1을 반환하고, 존재하지 않았다면 현재까지 걸린 일수(answer에 저장)을 반환한다.

return unripeTomato ? -1 : answer;

 

 

📌 사담 

- 런타임 에러때문에 시간이 많이 소요되었던 문제였다.

- 로직 자체에 문제가 있는줄 알고 많이 헤맸는데, 입력을 잘못 받아왔다는 것이 충격적이었다

- 프로그래머스에 익숙해서 항상 입력이 배열로 와서 그대로 사용하기만 했었는데 기본적인 입출력 실수를 해서 많이 부끄러웠다 

- 백준을 열심히 풀면서 더 연습해야겠다. 화이팅!

 

---