[JS] 백준 7576번 토마토

---

문제 링크

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

풀이 전략

보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.
하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다.
대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다.
철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.
정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터모든 토마토가 익어있는 상태이면 0
을 출력해야 하고,  토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

코드 

const fs = require("fs");
const [init, ...input] = fs
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n")
    .map((v) => v.split(" ").map(Number));

// queue 구현.
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);
        if (!this.head) {
            this.head = node;
        } else {
            this.rear.next = node;
        }
        this.rear = node;
        this.length++;
    }

    dequeue() {
        if (!this.head) {
            return false;
        }
        const data = this.head.data;
        this.head = this.head.next;
        this.length--;

        return data;
    }
}
//

const [n, m] = init;

solution(input);

function solution(arr) {
    const queue = new Queue();

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (arr[i][j] === 1) {
                queue.enqueue([i, j, 0]);
            }
        }
    }

    console.log(bfs(arr, queue));
}

function bfs(box, queue) {
    const dx = [-1, 0, 1, 0];
    const dy = [0, 1, 0, -1];
    // answer 를 0으로 초기화 해야 이미 모든 토마토가 익어있는 케이스를 포함할 수 있다.
    let answer = 0;

    while (queue.length) {
        const [x, y, day] = queue.dequeue();

        for (let i = 0; i < 4; i++) {
            const [nx, ny] = [x + dx[i], y + dy[i]];
            if (range_check(nx, ny) && box[nx][ny] === 0) {
                box[nx][ny] = 1;
                queue.enqueue([nx, ny, day + 1]);
            }
        }
        answer = day; // day를 계속해서 누적.
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (box[i][j] === 0) {
                // 익지 않은 토마토가 존재.
                return -1;
            }
        }
    }

    return answer;
}

function range_check(nx, ny) {
    if (0 <= nx && nx < m && 0 <= ny && ny < n) return true;
    else return false;
}

 

회고

bfs를 이용해서 최단 일수를 구해야하는 것은 알고 있었으나 그 일수를 어떻게 구해야하는가에 대한 고민이 부족했다. 결국, 다른 블로그를 참고하여 풀게 되었는데, 자바스크립트에 있는 배열 method중 Array.shift를 사용하게 되면 시간초과가 난다. 그래서 이를 해결하는 방법에는 직접 queue를 구현하거나 index를 사용하는 방법이 있다고 한다. 

다른 블로그에 나와있는 방법이 많았지만 나는 아직 이해할 수 없어 내가 가장 쉽다고 느꼈고 이해할 수 있는 코드를 짜보았다. 

 

더 좋은 방법이나 의견이 있으시다면 댓글 부탁드립니다 :)